import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class Euler396 {
    static final long K_MOD = 1000000000L;

    static long modPow(long base, long exp, long mod) {
        return BigInteger.valueOf(base)
                .modPow(BigInteger.valueOf(exp), BigInteger.valueOf(mod))
                .longValue();
    }

    static long modInv(long a, long mod) {
        return BigInteger.valueOf(a).modInverse(BigInteger.valueOf(mod)).longValue();
    }

    static class ModEntry {
        long mod;
        int pow2;
        int pow5;
        long period_mod;
        long mod2_part;
        long mod5_part;
        long inv_mod2_in5;

        ModEntry(long m, int p2, int p5, long pm, long m2p, long m5p) {
            this.mod = m;
            this.pow2 = p2;
            this.pow5 = p5;
            this.period_mod = pm;
            this.mod2_part = m2p;
            this.mod5_part = m5p;

            if (p2 > 0 && p5 > 0) {
                this.inv_mod2_in5 = modInv(m2p % m5p, m5p);
            } else {
                this.inv_mod2_in5 = 0;
            }
        }
    }

    static long pow5(int k) {
        long r = 1;
        for (int i = 0; i < k; i++)
            r *= 5;
        return r;
    }

    static List<ModEntry> buildModChain() {
        List<ModEntry> entries = new ArrayList<>();
        entries.add(new ModEntry(K_MOD, 9, 9, 4 * pow5(8), 1L << 9, pow5(9)));

        for (int e5 = 8; e5 >= 0; --e5) {
            long mod = 4 * pow5(e5);
            long period = (e5 == 0 ? 0 : 4 * pow5(e5 - 1));
            entries.add(new ModEntry(mod, 2, e5, period, 4, pow5(e5)));
        }
        return entries;
    }

    static long pow2ModComposite(ModEntry entry, long[] residues, List<ModEntry> chain, long exact_s,
            boolean exact_known) {
        if (entry.mod == 1)
            return 0;
        if (entry.pow5 == 0) {
            if (entry.pow2 == 0)
                return 0;
            if (exact_known && exact_s < entry.pow2) {
                return (1L << exact_s) % entry.mod;
            }
            return 0;
        }

        long exp_mod = 0;
        if (entry.period_mod > 0) {
            int idx = -1;
            for (int i = 0; i < chain.size(); i++) {
                if (chain.get(i).mod == entry.period_mod) {
                    idx = i;
                    break;
                }
            }
            exp_mod = residues[idx];
        }

        long p5 = modPow(2, exp_mod, entry.mod5_part);

        if (entry.pow2 == 0)
            return p5;

        long p2 = 0;
        if (exact_known && exact_s < entry.pow2) {
            p2 = (1L << exact_s) % entry.mod2_part;
        }

        long diff = (p5 - p2) % entry.mod5_part;
        long adjusted = (diff + entry.mod5_part) % entry.mod5_part;

        long t = BigInteger.valueOf(adjusted)
                .multiply(BigInteger.valueOf(entry.inv_mod2_in5))
                .mod(BigInteger.valueOf(entry.mod5_part))
                .longValue();

        long x = p2 + BigInteger.valueOf(entry.mod2_part)
                .multiply(BigInteger.valueOf(t))
                .mod(BigInteger.valueOf(entry.mod))
                .longValue();

        return x % entry.mod;
    }

    static long computeHMod(long s0, int m) {
        List<ModEntry> chain = buildModChain();
        long[] residues = new long[chain.size()];
        for (int i = 0; i < chain.size(); i++) {
            residues[i] = s0 % chain.get(i).mod;
        }

        long exact_s = s0;
        boolean exact_known = true;
        long kExactLimit = 1000;

        long sum_mod = 0;
        for (int i = 0; i <= m; i++) {
            long p_main = pow2ModComposite(chain.get(0), residues, chain, exact_s, exact_known);
            long term = BigInteger.valueOf(residues[0])
                    .multiply(BigInteger.valueOf((p_main + K_MOD - 1) % K_MOD))
                    .mod(BigInteger.valueOf(K_MOD))
                    .longValue();

            sum_mod = (sum_mod + term) % K_MOD;

            if (i == m)
                break;

            long[] next_residues = new long[chain.size()];
            for (int j = 0; j < chain.size(); j++) {
                long p = pow2ModComposite(chain.get(j), residues, chain, exact_s, exact_known);
                next_residues[j] = BigInteger.valueOf(residues[j])
                        .multiply(BigInteger.valueOf(p))
                        .mod(BigInteger.valueOf(chain.get(j).mod))
                        .longValue();
            }
            residues = next_residues;

            if (exact_known) {
                if (exact_s > 20) {
                    exact_known = false;
                } else {
                    long p2 = 1L << exact_s;
                    if (p2 > kExactLimit || exact_s > kExactLimit / Math.max(1, p2)) {
                        exact_known = false;
                    } else {
                        exact_s *= p2;
                        if (exact_s > kExactLimit) {
                            exact_known = false;
                        }
                    }
                }
            }
        }
        return sum_mod;
    }

    static long goodsteinSmall(int n) {
        long g = n;
        long base = 2;
        long count = 0;

        while (g > 0) {
            count++;
            List<Integer> digits = new ArrayList<>();
            long x = g;
            while (x > 0) {
                digits.add((int) (x % base));
                x /= base;
            }
            if (digits.isEmpty())
                digits.add(0);

            long nextVal = 0;
            for (int i = digits.size() - 1; i >= 0; i--) {
                nextVal = nextVal * (base + 1) + digits.get(i);
            }
            g = nextVal - 1;
            base++;
        }
        return count;
    }

    static long computeGMod(int n, long[] gSmall) {
        if (n < 8)
            return gSmall[n] % K_MOD;
        int low = n - 8;
        long t = gSmall[low];
        long s = t + 3;
        int m = (int) (t + 2);
        long h = computeHMod(s, m);
        return (t + h) % K_MOD;
    }

    static String solve() {
        long[] gSmall = new long[8];
        for (int n = 1; n < 8; n++) {
            gSmall[n] = goodsteinSmall(n);
        }

        long ans = 0;
        for (int n = 1; n < 16; n++) {
            ans = (ans + computeGMod(n, gSmall)) % K_MOD;
        }
        return Long.toString(ans);
    }

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