import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Euler671 {

    static final long MOD = 1000004321L;

    static class State {
        int rt, rb, pv, ct, cb;

        State(int rt, int rb, int pv, int ct, int cb) {
            this.rt = rt;
            this.rb = rb;
            this.pv = pv;
            this.ct = ct;
            this.cb = cb;
        }
    }

    static int encodeState(int rt, int rb, int pv, int ct, int cb, int k) {
        return ((((rt * 3 + rb) * 2 + pv) * k + ct) * k + cb);
    }

    static class MatrixData {
        int S;
        List<List<Integer>> adj;
    }

    static MatrixData buildMatrix(int k) {
        MatrixData md = new MatrixData();
        List<State> states = new ArrayList<>();
        HashMap<Integer, Integer> idMap = new HashMap<>();

        for (int rt = 0; rt <= 2; ++rt) {
            for (int rb = 0; rb <= 2; ++rb) {
                for (int pv = 0; pv <= 1; ++pv) {
                    for (int ct = 0; ct < k; ++ct) {
                        for (int cb = 0; cb < k; ++cb) {
                            boolean ok;
                            if (pv == 1) {
                                ok = (rt == 0 && rb == 0 && ct == cb);
                            } else {
                                ok = (ct != cb);
                            }
                            if (!ok)
                                continue;
                            int idx = states.size();
                            states.add(new State(rt, rb, pv, ct, cb));
                            idMap.put(encodeState(rt, rb, pv, ct, cb, k), idx);
                        }
                    }
                }
            }
        }

        md.S = states.size();
        md.adj = new ArrayList<>();
        for (int i = 0; i < md.S; ++i)
            md.adj.add(new ArrayList<>());

        for (int i = 0; i < md.S; ++i) {
            State s = states.get(i);
            if (s.rt > 0 && s.rb > 0) {
                md.adj.get(i).add(idMap.get(encodeState(s.rt - 1, s.rb - 1, 0, s.ct, s.cb, k)));
                continue;
            }
            if (s.rt > 0 && s.rb == 0) {
                for (int lb = 1; lb <= 3; ++lb) {
                    for (int cb = 0; cb < k; ++cb) {
                        if (cb == s.ct || cb == s.cb)
                            continue;
                        md.adj.get(i).add(idMap.get(encodeState(s.rt - 1, lb - 1, 0, s.ct, cb, k)));
                    }
                }
                continue;
            }
            if (s.rt == 0 && s.rb > 0) {
                for (int lt = 1; lt <= 3; ++lt) {
                    for (int ct = 0; ct < k; ++ct) {
                        if (ct == s.ct || ct == s.cb)
                            continue;
                        md.adj.get(i).add(idMap.get(encodeState(lt - 1, s.rb - 1, 0, ct, s.cb, k)));
                    }
                }
                continue;
            }

            for (int c = 0; c < k; ++c) {
                if (c == s.ct || c == s.cb)
                    continue;
                md.adj.get(i).add(idMap.get(encodeState(0, 0, 1, c, c, k)));
            }

            if (s.pv == 1) {
                for (int lt = 1; lt <= 3; ++lt) {
                    for (int lb = 1; lb <= 3; ++lb) {
                        for (int ct = 0; ct < k; ++ct) {
                            if (ct == s.ct)
                                continue;
                            for (int cb = 0; cb < k; ++cb) {
                                if (cb == s.cb || cb == ct)
                                    continue;
                                md.adj.get(i).add(idMap.get(encodeState(lt - 1, lb - 1, 0, ct, cb, k)));
                            }
                        }
                    }
                }
            }
        }

        return md;
    }

    static long modPow(long base, long exp) {
        long res = 1;
        long cur = base % MOD;
        while (exp > 0) {
            if ((exp & 1) != 0)
                res = (res * cur) % MOD;
            cur = (cur * cur) % MOD;
            exp >>= 1;
        }
        return res;
    }

    static long modInv(long x) {
        return modPow((x % MOD + MOD) % MOD, MOD - 2);
    }

    static List<Long> berlekampMassey(List<Long> s) {
        List<Long> C = new ArrayList<>();
        C.add(1L);
        List<Long> B = new ArrayList<>();
        B.add(1L);
        int L = 0, m = 1;
        long b = 1;

        for (int n = 0; n < s.size(); ++n) {
            long d = 0;
            for (int i = 0; i <= L; ++i) {
                d = (d + C.get(i) * s.get(n - i)) % MOD;
            }
            if (d == 0) {
                m++;
                continue;
            }
            List<Long> T = new ArrayList<>(C);
            long coef = (d * modInv(b)) % MOD;

            while (C.size() < B.size() + m)
                C.add(0L);

            for (int i = 0; i < B.size(); ++i) {
                long val = (C.get(i + m) + MOD - (coef * B.get(i)) % MOD) % MOD;
                C.set(i + m, val);
            }

            if (2 * L <= n) {
                L = n + 1 - L;
                B = T;
                b = d;
                m = 1;
            } else {
                m++;
            }
        }
        C.remove(0);
        for (int i = 0; i < C.size(); ++i)
            C.set(i, (MOD - C.get(i)) % MOD);
        return C;
    }

    static long[] combinePoly(long[] a, long[] b, long[] coef) {
        int L = coef.length;
        long[] res = new long[2 * L];
        for (int i = 0; i < L; ++i) {
            if (a[i] == 0)
                continue;
            for (int j = 0; j < L; ++j) {
                if (b[j] == 0)
                    continue;
                res[i + j] = (res[i + j] + a[i] * b[j]) % MOD;
            }
        }
        for (int i = 2 * L - 2; i >= L; --i) {
            if (res[i] == 0)
                continue;
            long val = res[i];
            for (int j = 1; j <= L; ++j) {
                res[i - j] = (res[i - j] + val * coef[j - 1]) % MOD;
            }
        }
        long[] out = new long[L];
        System.arraycopy(res, 0, out, 0, L);
        return out;
    }

    static long linearRec(List<Long> init, List<Long> coefList, long n) {
        int L = coefList.size();
        if (L == 0)
            return 0;
        if (n < init.size())
            return init.get((int) n);

        long[] coef = new long[L];
        for (int i = 0; i < L; ++i)
            coef[i] = coefList.get(i);

        long[] pol = new long[L];
        pol[0] = 1;

        long[] e = new long[L];
        if (L == 1) {
            e[0] = coef[0];
        } else {
            e[1] = 1;
        }

        long m = n;
        while (m > 0) {
            if ((m & 1) != 0)
                pol = combinePoly(pol, e, coef);
            e = combinePoly(e, e, coef);
            m >>= 1;
        }

        long res = 0;
        for (int i = 0; i < L; ++i) {
            res = (res + pol[i] * init.get(i)) % MOD;
        }
        return res;
    }

    static class Factor {
        long p;
        int e;

        Factor(long p, int e) {
            this.p = p;
            this.e = e;
        }
    }

    static List<Factor> factorize(long n) {
        List<Factor> res = new ArrayList<>();
        for (long p = 2; p * p <= n; p += (p == 2 ? 1 : 2)) {
            if (n % p == 0) {
                int cnt = 0;
                while (n % p == 0) {
                    n /= p;
                    cnt++;
                }
                res.add(new Factor(p, cnt));
            }
        }
        if (n > 1)
            res.add(new Factor(n, 1));
        return res;
    }

    static class Divisor {
        long d, phi;

        Divisor(long d, long phi) {
            this.d = d;
            this.phi = phi;
        }
    }

    static List<Divisor> genDivisors(List<Factor> factors) {
        List<Divisor> divs = new ArrayList<>();
        divs.add(new Divisor(1, 1));

        for (Factor f : factors) {
            List<Divisor> nextDivs = new ArrayList<>();
            for (Divisor dv : divs) {
                nextDivs.add(dv);
                long pPow = 1;
                long phiPow = 1;
                for (int i = 1; i <= f.e; ++i) {
                    pPow *= f.p;
                    phiPow = (i == 1) ? (f.p - 1) : (phiPow * f.p);
                    nextDivs.add(new Divisor(dv.d * pPow, dv.phi * phiPow));
                }
            }
            divs = nextDivs;
        }
        return divs;
    }

    static long solveProblem(int k, long n) {
        MatrixData md = buildMatrix(k);
        int S = md.S;

        long[][] P = new long[S][S];
        for (int i = 0; i < S; ++i)
            P[i][i] = 1;
        long[][] nextP = new long[S][S];

        List<Long> seq = new ArrayList<>();
        seq.add((long) S % MOD);

        int lastL = 0;
        int stable = 0;
        List<Long> coef = new ArrayList<>();

        for (int step = 1; step <= 2000; ++step) {
            for (int i = 0; i < S; ++i) {
                for (int j = 0; j < S; ++j)
                    nextP[i][j] = 0;
                for (int kIdx = 0; kIdx < S; ++kIdx) {
                    long val = P[i][kIdx];
                    if (val > 0) {
                        for (int to : md.adj.get(kIdx)) {
                            nextP[i][to] += val;
                        }
                    }
                }
                for (int j = 0; j < S; ++j)
                    nextP[i][j] %= MOD;
            }

            long[][] tmp = P;
            P = nextP;
            nextP = tmp;

            long tr = 0;
            for (int i = 0; i < S; ++i)
                tr = (tr + P[i][i]) % MOD;
            seq.add(tr);

            coef = berlekampMassey(seq);
            int L = coef.size();
            if (L == lastL)
                stable++;
            else {
                stable = 0;
                lastL = L;
            }

            if (L > 0 && seq.size() >= 2 * L + 5 && stable >= 5)
                break;
        }

        if (coef.isEmpty())
            coef.add(0L);

        List<Long> init = new ArrayList<>();
        for (int i = 0; i < coef.size(); ++i)
            init.add(seq.get(i));

        List<Divisor> divs = genDivisors(factorize(n));
        long total = 0;
        for (Divisor dv : divs) {
            long term = linearRec(init, coef, n / dv.d);
            total = (total + (dv.phi % MOD) * term) % MOD;
        }

        long invN = modInv(n % MOD);
        return (total * invN) % MOD;
    }

    public static String solve() {
        long n = 10004003002001L;
        return Long.toString(solveProblem(10, n));
    }

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