Problem: There have recently been elections in the zoo. Overall there were 7 main political parties: one of them is the Little Elephant Political Party, 6 other parties have less catchy names.

Political parties find their number in the ballot highly important. Overall there are m possible numbers: 1, 2, ..., m. Each of these 7 parties is going to be assigned in some way to exactly one number, at that, two distinct parties cannot receive the same number.

The Little Elephant Political Party members believe in the lucky digits 4 and 7. They want to evaluate their chances in the elections. For that, they need to find out, how many correct assignments are there, such that the number of lucky digits in the Little Elephant Political Party ballot number is strictly larger than the total number of lucky digits in the ballot numbers of 6 other parties. 

Help the Little Elephant Political Party, calculate this number. As the answer can be rather large, print the remainder from dividing it by 1000000007 (109 + 7).

Input

A single line contains a single positive integer m (7 ≤ m ≤ 109) — the number of possible numbers in the ballot.

Output

In a single line print a single integer — the answer to the problem modulo 1000000007 (109 + 7).

Examples

Input

7


Output

0


Input

8


Output

1440

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;

public class Task258B {
    private static long counts[] = new long[11];

    /**
     * @param args
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter output = new PrintWriter(System.out);

        String ms = input.readLine();

        counts = initCounts(ms);
        counts[0] -= 1; // subtracting the 0th number

        //output.write(Arrays.toString(counts));
        //output.write("\n");

        BigInteger result = solve();

        result = result.divideAndRemainder(BigInteger.valueOf(1000000007))[1];

        output.write(result.toString());
        output.write("\n");

        // output.write(width[0].multiply(height[0]).toString());

        output.close();
    }

    private static BigInteger solve() {

        BigInteger result = BigInteger.ZERO;

        for (int i = 1; i < 11; i++) {
            if (counts[i] == 0)
                break;
            //take number
            long myVariants = counts[i];
            counts[i] -= 1;

            for (int j = 1; j <= i; j++)
                result = result.add(BigInteger.valueOf(myVariants).multiply(giveAway(i - j, 6)));

            //return number;
            counts[i] += 1;
        }

        return result;
    }

    /**
     * gives away numbers with exactly _lucky_ count of lucky digits to _parties_ parties
     */
    private static BigInteger giveAway(int lucky, int parties) {
        if (parties == 0)
            return BigInteger.ZERO;

        if (lucky == 0) {
            //кол-во вариантов выбора X номеров из Y вариантов, где Y - кол-во номеров с нулем счастливых цифр
            //иначе говоря - размещения без повторений
            return _A_n_k(parties, counts[0]);
        }

        if (parties == 1)
            return BigInteger.valueOf(counts[lucky]);

        BigInteger otherVariants = BigInteger.ZERO;
        for (int i = lucky; i >= 0; i--) {
            BigInteger next1 = giveAway(i, 1);
            counts[i] -= 1;
            BigInteger next2 = giveAway(lucky - i, parties - 1);
            counts[i] += 1;
            otherVariants = otherVariants.add(next1.multiply(next2));
        }
        return otherVariants;
    }

    //формула размещений из n по k
    private static BigInteger _A_n_k(long n, long k) { //n parties, k variants
        if (k < n)
            return BigInteger.ZERO;
        BigInteger result = BigInteger.ONE;
        for (int i = 0; i < n; i++) {
            result = result.multiply(BigInteger.valueOf(k - i));
        }
        return result;
    }

    private static long[] initCounts(String ms) {
        // f(XYZ) = f(X00) # f(YZ)

        long[] result = new long[11];

        // recursion exit
        if (ms.length() < 2) {
            int m = Integer.valueOf(ms);
            int lucky = howManyLucky(m);
            result[1] += lucky;
            result[0] += m - lucky + 1; // "+1" to count zero
            return result;
        }

        int first = Integer.valueOf(ms.substring(0, 1));
        int firstLucky = (first == 4 || first == 7) ? 1 : 0;

        // f(YZ)
        long[] fYZ = initCounts(ms.substring(1));
        for (int i = 0; i < 9; i++) {
            result[firstLucky + i] += fYZ[i];
        }

        int lucky = howManyLucky(first - 1);
        int notLucky = first - lucky; // 0 is valid, that's why no "-1"

        long[] f999 = initCounts("" + (BigInteger.valueOf(10).pow(ms.substring(1).length()).intValue() - 1)); // getting closest 9999 before X00
        for (int i = 0; i < 10; i++) {
            result[i + 1] += lucky * f999[i];
            result[i] += notLucky * f999[i];
        }

        return result;
    }

    /**
     * checks how many lucky digits before (inclusive) given digit
     */
    private static int howManyLucky(int digit) {
        if (digit > 6) {
            return 2;
        } else if (digit > 3) {
            return 1;
        } else {
            return 0;
        }
    }
}