200919土[BOJ]10844

BOJ 10844

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {	
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	int N = Integer.parseInt(br.readLine());
    	br.close();
    	
    	long f[][] = new long[N+1][10];
    	
    	for(int i=1;i<=9;i++) {
    		f[1][i] = 1;
    	}
    	
    	for(int i=2;i<=N;i++) {
    		for(int j=0;j<10;j++) {
    			if(j==0) {
    				f[i][j] = f[i-1][j+1] % 1000000000;
    			} else if (j==9) {
    				f[i][j] = f[i-1][j-1] % 1000000000;
    			} else {
    				f[i][j] = (f[i-1][j-1] + f[i-1][j+1]) % 1000000000;
    			}
    		}
    	}
    	long sum = 0;
    	for(int i=0;i<10;i++) {
    		sum += f[N][i];
    	}
    	System.out.println(sum%1000000000);
    	
    }
}