import java.util.Arrays;
import java.util.Scanner;

public class POLY {

private static int[][] cache = new int[101][101];

private static int n;

private static final int MOD = 10000000;

public static void main(String[] args) {
    // TODO Auto-generated method stub

    Scanner sc = new Scanner(System.in);

    int C = sc.nextInt();

    for (int i = 0; i < C; i++) {

        n = sc.nextInt();

        for (int j = 0; j < 101; j++) {
            Arrays.fill(cache[j], -1);
        }

        System.out.println(maxPoly());

    }
}

private static int poly(int n, int first) {

    if (n == first)     return 1;

    if (cache[n][first] != -1)  return cache[n][first];

    int ret = cache[n][first] = 0;

    for (int second = 1; second <= n-first; second++) {
        int add = second + first - 1;
        add *= poly(n - first, second);
        add %= MOD;
        cache[n][first] = (ret += add);
        cache[n][first] = (ret %= MOD);
    }

    return ret;
}

private static int maxPoly() {
    int ret = 0;
    for (int j = 1; j <= n; j++) {
        ret += (poly(n, j) % MOD);
    }

    return ret;
}

}

코드는 정상적으로 짠거같은데 예제 3번째 입력

92에 대해서 예제 출력인 4841817이 나오지 않고

394841817가 출력이 됩니다.

맞게 코드를 짰다고 생각하는데.. 제가 놓친 부분이 있을런지요..?