public class Euler467 {
    public static String solve() {
        int kMod = 1000000007;
        int n = 10000;

        int limit = 150000;
        boolean[] isPrime = new boolean[limit + 1];
        for (int i = 2; i <= limit; i++)
            isPrime[i] = true;

        for (int p = 2; p * p <= limit; p++) {
            if (isPrime[p]) {
                for (int i = p * p; i <= limit; i += p) {
                    isPrime[i] = false;
                }
            }
        }

        byte[] primeDigits = new byte[n];
        byte[] compositeDigits = new byte[n];
        int pCount = 0;
        int cCount = 0;

        for (int x = 2; x <= limit; x++) {
            if (isPrime[x]) {
                if (pCount < n) {
                    primeDigits[pCount++] = (byte) (1 + (x - 1) % 9);
                }
            } else {
                if (cCount < n) {
                    compositeDigits[cCount++] = (byte) (1 + (x - 1) % 9);
                }
            }
            if (pCount == n && cCount == n)
                break;
        }

        int width = n + 1;
        short[] dp = new short[width * width];

        for (int i = n; i >= 0; i--) {
            int rowOffset = i * width;
            int nextRowOffset = (i + 1) * width;
            byte pi = i < n ? primeDigits[i] : 0;

            for (int j = n; j >= 0; j--) {
                int at = rowOffset + j;
                if (i == n) {
                    dp[at] = (short) (n - j);
                    continue;
                }
                if (j == n) {
                    dp[at] = (short) (n - i);
                    continue;
                }

                if (pi == compositeDigits[j]) {
                    dp[at] = (short) (1 + dp[nextRowOffset + j + 1]);
                } else {
                    short da = dp[nextRowOffset + j];
                    short db = dp[rowOffset + j + 1];
                    dp[at] = (short) (1 + (da < db ? da : db));
                }
            }
        }

        int i = 0;
        int j = 0;
        long resultMod = 0;

        while (i < n || j < n) {
            byte digit;
            if (i == n) {
                digit = compositeDigits[j++];
            } else if (j == n) {
                digit = primeDigits[i++];
            } else if (primeDigits[i] == compositeDigits[j]) {
                digit = primeDigits[i];
                i++;
                j++;
            } else {
                short da = dp[(i + 1) * width + j];
                short db = dp[i * width + j + 1];
                if (da < db || (da == db && primeDigits[i] < compositeDigits[j])) {
                    digit = primeDigits[i++];
                } else {
                    digit = compositeDigits[j++];
                }
            }
            resultMod = (resultMod * 10 + digit) % kMod;
        }

        return Long.toString(resultMod);
    }

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