[백준] 쉬운 계단 수 - 10844 (JAVA)

answer %= 1000000000를 빼먹어서 틀렸다...

import java.io.*;
import java.util.StringTokenizer;

public class Main {
static int[][] answers;

public static void main(String... args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer tokenizer = new StringTokenizer(br.readLine());
    br.close();
    int n = Integer.parseInt(tokenizer.nextToken());
    answers = new int[n+1][10];
    for (int i = 1; i < 10; i++) {
        answers[1][i] = 1;
    }


    int answer = 0;
    for (int i = 0; i < 10; i++) {
        answer += f(n, i) ;
        answer %= 1000000000 ;
    }
    bw.write(String.valueOf(answer));

    bw.flush();
    bw.close();
}

static int f(int n, int d) {
    if (n < 0) {
        return 0;
    }
    if (answers[n][d] != 0) {
        return answers[n][d];
    }

    if (d == 0) {
        answers[n][d] = f(n-1, d+1);
    } else if (d == 9) {
        answers[n][d] = f(n-1,  d-1);
    } else {
        answers[n][d] = f(n-1,  d-1) + f(n-1, d+1);
    }
    answers[n][d] %= 1000000000;

    return answers[n][d];
}

}