public class Euler258 {
    static final int K = 2000;
    static final int MOD = 20092010;

    static long[] multiplyMod(long[] a, long[] b) {
        long[] tmp = new long[2 * K];

        for (int i = 0; i < K; ++i) {
            long ai = a[i];
            if (ai == 0)
                continue;
            for (int j = 0; j < K; ++j) {
                long bj = b[j];
                if (bj == 0)
                    continue;
                tmp[i + j] = (tmp[i + j] + ai * bj) % MOD;
            }
        }

        for (int i = 2 * K - 1; i >= K; --i) {
            long v = tmp[i];
            if (v == 0)
                continue;
            tmp[i - K] = (tmp[i - K] + v) % MOD;
            tmp[i - K + 1] = (tmp[i - K + 1] + v) % MOD;
        }

        long[] out = new long[K];
        System.arraycopy(tmp, 0, out, 0, K);
        return out;
    }

    public static String solve() {
        long index = 1_000_000_000_000_000_000L;
        if (index < K) {
            return String.valueOf(1 % MOD);
        }

        long[] acc = new long[K];
        acc[0] = 1;

        long[] base = new long[K];
        base[1] = 1;

        long exp = index;
        while (exp > 0) {
            if ((exp & 1) != 0) {
                acc = multiplyMod(acc, base);
            }
            exp >>= 1;
            if (exp > 0) {
                base = multiplyMod(base, base);
            }
        }

        long answer = 0;
        for (long c : acc) {
            answer += c;
        }
        answer %= MOD;

        return String.valueOf(answer);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}