49 lines
1.6 KiB
Java
49 lines
1.6 KiB
Java
import java.util.*;
|
|
|
|
public class _1562 {
|
|
public static void main(String[] args) {
|
|
Scanner sc = new Scanner(System.in);
|
|
int N = sc.nextInt();
|
|
sc.close();
|
|
|
|
if(N <= 10) {
|
|
System.out.println(N/10);
|
|
return;
|
|
}
|
|
|
|
long MOD = 1000000000;
|
|
long[][][] dp = new long[N+1][10][1024];
|
|
for(int i=1; i<10; i++) dp[1][i][1<<i] = 1;
|
|
|
|
|
|
for(int length = 1; length < N; length++) {
|
|
for(int last_num = 0; last_num < 10; last_num++) {
|
|
for(int bit_state = 0; bit_state < 1024; bit_state++) {
|
|
if(dp[length][last_num][bit_state] == 0) continue;
|
|
|
|
int next_num = last_num + 1;
|
|
if(0<=next_num && next_num<=9) {
|
|
int next_bit_state = bit_state | (1<<next_num);
|
|
dp[length+1][next_num][next_bit_state] += dp[length][last_num][bit_state];
|
|
dp[length+1][next_num][next_bit_state] %= MOD;
|
|
}
|
|
|
|
next_num = last_num - 1;
|
|
if(0<=next_num && next_num<=9) {
|
|
int next_bit_state = bit_state | (1<<next_num);
|
|
dp[length+1][next_num][next_bit_state] += dp[length][last_num][bit_state];
|
|
dp[length+1][next_num][next_bit_state] %= MOD;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
long ans = 0;
|
|
for(int i=0; i<10; i++) {
|
|
ans += dp[N][i][1023];
|
|
ans %= MOD;
|
|
}
|
|
System.out.println(ans);
|
|
}
|
|
}
|