public class Euler709 {
    static final int kMod = 1020202009;

    public static String solve() {
        int n = 24680;
        if (n == 0)
            return "1";

        int[] prev = new int[n + 1];
        int[] curr = new int[n + 1];
        prev[0] = 1;

        for (int row = 1; row <= n; ++row) {
            curr[0] = 0;
            for (int k = 1; k <= row; ++k) {
                int v = curr[k - 1] + prev[row - k];
                if (v >= kMod) {
                    v -= kMod;
                }
                curr[k] = v;
            }
            int[] temp = prev;
            prev = curr;
            curr = temp;
        }

        return Integer.toString(prev[n]);
    }

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