import java.math.BigInteger;
import java.util.*;

public class Euler924 {

    static final long kMod = 1000000007L;
    static final long kTailMod = 100000000000L;
    static final long kTailCycleLen = 15625000L;
    static final long kTargetN = 10000000000000000L;

    static long stepMod(long x, long mod) {
        if (mod == kMod) {
            return (x * x + 2) % mod;
        } else {
            BigInteger bigX = BigInteger.valueOf(x);
            return bigX.multiply(bigX).add(BigInteger.valueOf(2)).remainder(BigInteger.valueOf(mod)).longValue();
        }
    }

    static class CycleData {
        long mu = 0;
        long lambda_ = 0;
        List<Long> values = new ArrayList<>();
        List<Long> prefMod = new ArrayList<>();
    }

    static CycleData buildCycleModP() {
        CycleData data = new CycleData();
        Map<Long, Long> seen = new HashMap<>();
        long x = 0;
        seen.put(x, 0L);
        data.values.add(x);

        long idx = 1;
        while (true) {
            x = stepMod(x, kMod);
            if (seen.containsKey(x)) {
                data.mu = seen.get(x);
                data.lambda_ = idx - seen.get(x);
                break;
            }
            seen.put(x, idx);
            data.values.add(x);
            idx++;
        }

        data.prefMod = new ArrayList<>(Collections.nCopies(data.values.size() + 1, 0L));
        for (int i = 0; i < data.values.size(); i++) {
            data.prefMod.set(i + 1, (data.prefMod.get(i) + data.values.get(i)) % kMod);
        }
        return data;
    }

    static long prefixSumCycle(CycleData data, long n) {
        if (n + 1 <= data.values.size()) {
            return data.prefMod.get((int) (n + 1));
        }

        long mu = data.mu;
        long lambda_ = data.lambda_;
        long sumMu = data.prefMod.get((int) mu);
        long cycleSum = (data.prefMod.get((int) (mu + lambda_)) - data.prefMod.get((int) mu) + kMod) % kMod;

        long remaining = n - mu + 1;
        long fullCycles = remaining / lambda_;
        long rem = remaining % lambda_;

        long total = sumMu;
        total = (total + (fullCycles % kMod) * cycleSum) % kMod;
        long partial = (data.prefMod.get((int) (mu + rem)) - data.prefMod.get((int) mu) + kMod) % kMod;
        total = (total + partial) % kMod;
        return total;
    }

    static long rangeSumCycle(CycleData data, long left, long right) {
        if (right < left)
            return 0;
        long prefR = prefixSumCycle(data, right);
        long prefL = left == 0 ? 0 : prefixSumCycle(data, left - 1);
        return (prefR - prefL + kMod) % kMod;
    }

    static boolean nextPermutation(char[] array) {
        int i = array.length - 2;
        while (i >= 0 && array[i] >= array[i + 1]) {
            i--;
        }
        if (i < 0)
            return false;

        int j = array.length - 1;
        while (array[j] <= array[i]) {
            j--;
        }

        char temp = array[i];
        array[i] = array[j];
        array[j] = temp;

        for (int l = i + 1, r = array.length - 1; l < r; l++, r--) {
            temp = array[l];
            array[l] = array[r];
            array[r] = temp;
        }
        return true;
    }

    static long sumSmallExact(long n_limit) {
        long total = 0;
        BigInteger a = BigInteger.ZERO;
        long upto = Math.min(n_limit, 5L);
        for (int i = 0; i < upto; i++) {
            a = a.multiply(a).add(BigInteger.valueOf(2));
            char[] s = a.toString().toCharArray();
            if (nextPermutation(s)) {
                BigInteger val = new BigInteger(new String(s));
                total = (total + val.remainder(BigInteger.valueOf(kMod)).longValue()) % kMod;
            }
        }
        return total;
    }

    static long sumATerms(long n_limit, CycleData mod_p_cycle) {
        if (n_limit < 6)
            return 0;
        return rangeSumCycle(mod_p_cycle, 6, n_limit);
    }

    static class PermDelta {
        boolean ok;
        long delta;

        PermDelta(boolean ok, long delta) {
            this.ok = ok;
            this.delta = delta;
        }
    }

    static PermDelta nextPermDelta11(long tail) {
        char[] d = new char[11];
        long x = tail;
        for (int i = 10; i >= 0; i--) {
            d[i] = (char) ('0' + (x % 10));
            x /= 10;
        }

        if (!nextPermutation(d))
            return new PermDelta(false, 0);

        long nextTail = 0;
        for (int i = 0; i < 11; i++) {
            nextTail = nextTail * 10 + (d[i] - '0');
        }
        return new PermDelta(true, nextTail - tail);
    }

    static long sumDeltaTerms(long n_limit) {
        if (n_limit < 6)
            return 0;

        long a5Tail = 0;
        for (int i = 0; i < 5; i++) {
            a5Tail = stepMod(a5Tail, kTailMod);
        }

        long count = n_limit - 5;
        long cycleSum = 0;
        long tail = a5Tail;

        for (long i = 0; i < kTailCycleLen; i++) {
            tail = stepMod(tail, kTailMod);
            PermDelta pd = nextPermDelta11(tail);
            cycleSum = (cycleSum + pd.delta % kMod) % kMod;
        }

        long fullCycles = count / kTailCycleLen;
        long rem = count % kTailCycleLen;

        long total = ((fullCycles % kMod) * cycleSum) % kMod;

        tail = a5Tail;
        for (long i = 0; i < rem; i++) {
            tail = stepMod(tail, kTailMod);
            PermDelta pd = nextPermDelta11(tail);
            total = (total + pd.delta % kMod) % kMod;
        }

        return total;
    }

    public static String solve(long n_limit) {
        CycleData modPCycle = buildCycleModP();
        long answer = 0;
        answer = (answer + sumSmallExact(n_limit)) % kMod;
        answer = (answer + sumATerms(n_limit, modPCycle)) % kMod;
        answer = (answer + sumDeltaTerms(n_limit)) % kMod;
        return Long.toString(answer);
    }

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