-
Notifications
You must be signed in to change notification settings - Fork 3
/
1798.cpp
24 lines (24 loc) · 1.02 KB
/
1798.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1010, mod = 1000000007;
ll dp[maxn][2][3];
int main(){
//freopen("../input.txt", "r", stdin);
ll n; cin>>n;
memset(dp, 0, sizeof(dp));
dp[1][0][0] = 9, dp[1][0][1] = 1;
for(int i = 1; i < n; i++) {
if(dp[i][0][0]) dp[i + 1][0][0] += 9 * dp[i][0][0], dp[i + 1][0][1] += dp[i][0][0];
if(dp[i][0][1]) dp[i + 1][0][0] += 9 * dp[i][0][1], dp[i + 1][0][2] += dp[i][0][1];
if(dp[i][0][2]) dp[i + 1][0][0] += 9 * dp[i][0][2], dp[i + 1][1][2] += dp[i][0][2];
if(dp[i][1][0]) dp[i + 1][1][0] += 9 * dp[i][1][0], dp[i + 1][1][1] += dp[i][1][0];
if(dp[i][1][1]) dp[i + 1][1][0] += 9 * dp[i][1][1], dp[i + 1][1][2] += dp[i][1][1];
if(dp[i][1][2]) dp[i + 1][1][0] += 9 * dp[i][1][2];
for(int a = 0; a < 2; a++) for(int b = 0; b < 3; b++) dp[i + 1][a][b] %= mod;
}
ll ans = 0;
for(int i = 0; i < 3; i++) ans += dp[n][1][i], ans %= mod;
cout<<(ans + mod) % mod<<endl;
return 0;
}