29 lines
734 B
Java
29 lines
734 B
Java
import java.util.Scanner;
|
|
|
|
public class _10844 {
|
|
public static void main(String[] args) {
|
|
Scanner sc = new Scanner(System.in);
|
|
int N = sc.nextInt();
|
|
sc.close();
|
|
|
|
long MOD = 1000000000;
|
|
long[][] dp = new long[N+1][10];
|
|
for(int i=1; i<10; i++) dp[1][i] = 1;
|
|
|
|
for(int i=2; i<=N; i++) {
|
|
for(int j=0; j<10; j++) {
|
|
if(j==0) dp[i][j] = dp[i-1][1]%MOD;
|
|
else if(j==9) dp[i][j] = dp[i-1][8]%MOD;
|
|
else dp[i][j] = dp[i-1][j-1]%MOD + dp[i-1][j+1]%MOD;
|
|
}
|
|
}
|
|
|
|
long res = 0;
|
|
for (long n : dp[N]) {
|
|
res += n;
|
|
res %= MOD;
|
|
}
|
|
System.out.println(res);
|
|
}
|
|
}
|