import java.math.BigDecimal;
import java.math.MathContext;
import java.math.RoundingMode;
import java.util.*;

public class Euler827 {

    static final long kMod = 409120391L;
    static final MathContext MC = new MathContext(100, RoundingMode.HALF_UP);

    static class Rep {
        boolean valid = false;
        BigDecimal log2v = BigDecimal.ZERO;
        ArrayList<Long> exps = new ArrayList<>();
    }

    static class BestD {
        boolean valid = false;
        BigDecimal log2v = BigDecimal.ZERO;
        long e2 = 0;
        Rep rep3;
    }

    static class QRep {
        boolean valid = false;
        BigDecimal log2v = BigDecimal.ZERO;
        Rep rep1 = new Rep();
        long e2 = 0;
        Rep rep3 = new Rep();
    }

    static long mulMod(long a, long b, long mod) {
        // use Math.multiplyHigh / 128-bit mul
        long q = (long) ((double) a * b / mod);
        long r = a * b - q * mod;
        while (r < 0)
            r += mod;
        while (r >= mod)
            r -= mod;
        return r;
    }

    static long powMod(long a, long e, long mod) {
        long r = 1 % mod;
        a %= mod;
        while (e > 0) {
            if ((e & 1L) == 1L) {
                r = mulMod(r, a, mod);
            }
            a = mulMod(a, a, mod);
            e >>= 1L;
        }
        return r;
    }

    static boolean isPrime64(long n) {
        if (n < 2)
            return false;
        long[] smallPrimes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 };
        for (long p : smallPrimes) {
            if (n % p == 0)
                return n == p;
        }

        long d = n - 1;
        int s = 0;
        while ((d & 1L) == 0) {
            d >>= 1L;
            s++;
        }

        long[] bases = { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 };
        for (long a : bases) {
            if (a % n == 0)
                continue;
            long x = powMod(a, d, n);
            if (x == 1 || x == n - 1)
                continue;
            boolean comp = true;
            for (int r = 1; r < s; ++r) {
                x = mulMod(x, x, n);
                if (x == n - 1) {
                    comp = false;
                    break;
                }
            }
            if (comp)
                return false;
        }
        return true;
    }

    static Random rng = new Random(0);

    static long pollardRho(long n) {
        if ((n & 1L) == 0)
            return 2;
        if (n % 3 == 0)
            return 3;
        if (n % 5 == 0)
            return 5;

        while (true) {
            long c = 2 + (long) (rng.nextDouble() * (n - 3));
            long x = 2 + (long) (rng.nextDouble() * (n - 3));
            long y = x;
            long d = 1;

            while (d == 1) {
                x = (mulMod(x, x, n) + c) % n;
                y = (mulMod(y, y, n) + c) % n;
                y = (mulMod(y, y, n) + c) % n;
                long diff = x > y ? x - y : y - x;
                d = gcd(diff, n);
            }
            if (d != n)
                return d;
        }
    }

    static long gcd(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    static void factorRec(long n, Map<Long, Integer> out) {
        if (n == 1)
            return;
        if (isPrime64(n)) {
            out.put(n, out.getOrDefault(n, 0) + 1);
            return;
        }
        long d = pollardRho(n);
        factorRec(d, out);
        factorRec(n / d, out);
    }

    static Map<Long, ArrayList<Long>> oddDivCache = new HashMap<>();

    static ArrayList<Long> oddDivisors(long n) {
        if (oddDivCache.containsKey(n)) {
            return oddDivCache.get(n);
        }

        Map<Long, Integer> fac = new HashMap<>();
        factorRec(n, fac);

        ArrayList<Long> divs = new ArrayList<>();
        divs.add(1L);

        for (Map.Entry<Long, Integer> entry : fac.entrySet()) {
            long p = entry.getKey();
            int e = entry.getValue();

            ArrayList<Long> next = new ArrayList<>();
            long pe = 1;
            for (int i = 0; i <= e; ++i) {
                for (long d : divs) {
                    next.add(d * pe);
                }
                pe *= p;
            }
            divs = next;
        }

        ArrayList<Long> odd = new ArrayList<>();
        for (long d : divs) {
            if ((d & 1L) != 0) {
                odd.add(d);
            }
        }
        Collections.sort(odd);
        oddDivCache.put(n, odd);
        return odd;
    }

    static ArrayList<Long> primesMod4(int residue, int count) {
        ArrayList<Long> ps = new ArrayList<>();
        for (long x = 2; ps.size() < count; ++x) {
            if (x % 4 != residue)
                continue;
            boolean prime = true;
            for (long p = 2; p * p <= x; ++p) {
                if (x % p == 0) {
                    prime = false;
                    break;
                }
            }
            if (prime)
                ps.add(x);
        }
        return ps;
    }

    static ArrayList<Long> P1;
    static ArrayList<Long> P3;

    static BigDecimal[] ln_table;

    static void initLogs(int max_val) {
        ln_table = new BigDecimal[max_val + 1];
        ln_table[1] = BigDecimal.ZERO;
        BigDecimal eps = new BigDecimal("1e-100");
        for (int k = 2; k <= max_val; ++k) {
            BigDecimal z = BigDecimal.ONE.divide(BigDecimal.valueOf(2L * k - 1), MC);
            BigDecimal z2 = z.multiply(z, MC);
            BigDecimal sum = BigDecimal.ZERO;
            BigDecimal term = z;
            int i = 0;
            while (true) {
                BigDecimal add = term.divide(BigDecimal.valueOf(2L * i + 1), MC);
                if (add.compareTo(eps) < 0) {
                    break;
                }
                sum = sum.add(add, MC);
                term = term.multiply(z2, MC);
                i++;
            }
            sum = sum.multiply(BigDecimal.valueOf(2), MC);
            ln_table[k] = ln_table[k - 1].add(sum, MC);
        }
    }

    static BigDecimal[] L1;
    static BigDecimal[] L3;
    static final BigDecimal LOG2_2 = BigDecimal.ONE;

    static BigDecimal[] makeLogs(ArrayList<Long> ps) {
        BigDecimal ln2 = ln_table[2];
        BigDecimal[] logs = new BigDecimal[ps.size()];
        for (int i = 0; i < ps.size(); ++i) {
            logs[i] = ln_table[ps.get(i).intValue()].divide(ln2, MC);
        }
        return logs;
    }

    static class DfsKey {
        long rem;
        int idx;
        long prevf;

        DfsKey(long rem, int idx, long prevf) {
            this.rem = rem;
            this.idx = idx;
            this.prevf = prevf;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;
            DfsKey dfsKey = (DfsKey) o;
            return rem == dfsKey.rem && idx == dfsKey.idx && prevf == dfsKey.prevf;
        }

        @Override
        public int hashCode() {
            return Objects.hash(rem, idx, prevf);
        }
    }

    static Rep solveProduct(long P_val, ArrayList<Long> primes, BigDecimal[] logs, Map<Long, Rep> top_cache) {
        if (P_val == 1) {
            Rep r = new Rep();
            r.valid = true;
            r.log2v = BigDecimal.ZERO;
            return r;
        }

        if (top_cache.containsKey(P_val)) {
            return top_cache.get(P_val);
        }

        Map<DfsKey, Rep> memo = new HashMap<>();

        class DFS {
            Rep dfs(long rem, int idx, long prevf) {
                if (rem == 1) {
                    Rep base = new Rep();
                    base.valid = true;
                    base.log2v = BigDecimal.ZERO;
                    return base;
                }
                if (idx >= primes.size()) {
                    return new Rep();
                }

                DfsKey key = new DfsKey(rem, idx, prevf);
                if (memo.containsKey(key)) {
                    return memo.get(key);
                }

                Rep best = new Rep();

                ArrayList<Long> divs = oddDivisors(rem);
                for (int i = divs.size() - 1; i >= 0; i--) {
                    long f = divs.get(i);
                    if (f == 1 || f > prevf)
                        continue;
                    long e = (f - 1) / 2;
                    if (e == 0)
                        continue;

                    Rep sub = dfs(rem / f, idx + 1, f);
                    if (!sub.valid)
                        continue;

                    Rep cand = new Rep();
                    cand.valid = true;
                    cand.log2v = logs[idx].multiply(BigDecimal.valueOf(e), MC).add(sub.log2v, MC);
                    cand.exps.add(e);
                    cand.exps.addAll(sub.exps);

                    if (!best.valid || cand.log2v.compareTo(best.log2v) < 0) {
                        best = cand;
                    }
                }

                memo.put(key, best);
                return best;
            }
        }

        DFS obj = new DFS();
        Rep res = obj.dfs(P_val, 0, P_val);
        top_cache.put(P_val, res);
        return res;
    }

    static Map<Long, Rep> cacheRep1 = new HashMap<>();
    static Map<Long, Rep> cacheRep3 = new HashMap<>();
    static Map<Long, BestD> cacheBestD = new HashMap<>();

    static BestD bestForD(long D) {
        if (cacheBestD.containsKey(D)) {
            return cacheBestD.get(D);
        }

        BestD best = new BestD();
        ArrayList<Long> divs = oddDivisors(D);
        for (long a2 : divs) {
            long e2 = 0;
            BigDecimal part2 = BigDecimal.ZERO;
            if (a2 > 1) {
                e2 = (a2 + 1) / 2;
                part2 = LOG2_2.multiply(BigDecimal.valueOf(e2), MC);
            }

            long C = D / a2;
            Rep rep3 = solveProduct(C, P3, L3, cacheRep3);
            if (!rep3.valid)
                continue;

            BigDecimal cur = part2.add(rep3.log2v, MC);
            if (!best.valid || cur.compareTo(best.log2v) < 0) {
                best.valid = true;
                best.log2v = cur;
                best.e2 = e2;
                best.rep3 = rep3;
            }
        }

        cacheBestD.put(D, best);
        return best;
    }

    static QRep Qrep(long n) {
        long S = n + 1;
        QRep best = new QRep();
        ArrayList<Long> divs = oddDivisors(S);

        for (long B : divs) {
            Rep rep1 = solveProduct(B, P1, L1, cacheRep1);
            if (!rep1.valid)
                continue;

            long D = (2 * S) / B - 1;
            BestD bd = bestForD(D);
            if (!bd.valid)
                continue;

            BigDecimal cur = rep1.log2v.add(bd.log2v, MC);
            if (!best.valid || cur.compareTo(best.log2v) < 0) {
                best.valid = true;
                best.log2v = cur;
                best.rep1 = rep1;
                best.e2 = bd.e2;
                best.rep3 = bd.rep3;
            }
        }

        return best;
    }

    static long repMod(Rep rep, ArrayList<Long> primes, long mod) {
        long r = 1;
        for (int i = 0; i < rep.exps.size(); ++i) {
            r = mulMod(r, powMod(primes.get(i), rep.exps.get(i), mod), mod);
        }
        return r;
    }

    static long Qmod(long n) {
        QRep qr = Qrep(n);
        long r = repMod(qr.rep1, P1, kMod);
        r = mulMod(r, powMod(2, qr.e2, kMod), kMod);
        r = mulMod(r, repMod(qr.rep3, P3, kMod), kMod);
        return r;
    }

    public static String solve() {
        P1 = primesMod4(1, 80);
        P3 = primesMod4(3, 80);
        long maxPrime = 0;
        for (long p : P1)
            maxPrime = Math.max(maxPrime, p);
        for (long p : P3)
            maxPrime = Math.max(maxPrime, p);

        initLogs((int) maxPrime + 10);
        L1 = makeLogs(P1);
        L3 = makeLogs(P3);

        long ans = 0;
        for (int k = 1; k <= 18; ++k) {
            long n = 1;
            for (int i = 0; i < k; ++i)
                n *= 10L;
            ans += Qmod(n);
            ans %= kMod;
        }
        return Long.toString(ans);
    }

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