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.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * 4 4
 * 1 5 3 4
 * 1 2
 * 1 3
 * 2 3
 * 3 3
 *
 *
 * @author pttrung
 */
public class A {

    public static long Mod = (long) (1e9) + 7;
    static int time = 0;
    static int[][][][] dp;
    static boolean[][] check;

    public static void main(String[] args) throws FileNotFoundException {
        PrintWriter out = new PrintWriter(System.out);
        Scanner in = new Scanner();

        String n = in.next();
        int m = n.length();
        dp = new int[m][2][2][m + 1];
        for (int[][][] a : dp) {
            for (int[][] b : a) {
                for (int[] c : b) {
                    Arrays.fill(c, -1);
                }
            }
        }
//        int[]test = new int[n.length() + 1];
//        for(int i = 1; i <= Integer.parseInt(n); i++){
//            String v = "" + i;
//            int co = 0;
//            for(int j = 0; j <v.length(); j++ ){
//                if(v.charAt(j) == '4' || v.charAt(j) == '7'){
//                    co++;
//                }
//            }
//            test[co]++;
//        }
        long[] count = new long[m + 1];
        for (int i = 0; i <= m; i++) {
            count[i] = cal(0, 0, 0, i, n);
          //  System.out.println(count[i] + " " + i + " " + test[i]);
            count[i] %= Mod;
        }
        long[][] c = new long[7][7];
        c[0][0] = 1;
        for (int i = 1; i < 7; i++) {
            c[i][0] = 1;
            c[i][i] = 1;
            for (int j = 1; j < i; j++) {
                c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
                c[i][j] %= Mod;
            }
        }
        long result = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j < i; j++) {
                for (int k = j; j + k < i; k++) {
                    for (int h = k; h + j + k < i; h++) {
                        for (int g = h; g + h + j + k < i; g++) {
                            for (int u = g; u + g + h + j + k < i; u++) {
                                for (int l = u; l + u + g + h + j + k < i; l++) {
                                   //System.out.println(i + " " + j + " " + k + " " + u + " " + l + " " + g + " " + h);
                                    long[] cur = new long[m + 1];
                                    long tmp = count[i];
                                    //cur[i]++;
                                    tmp *= ((count[j] - cur[j] + Mod) % Mod);
                                    tmp %= Mod;
                                    cur[j]++;
                                    tmp *= ((count[k] - cur[k] + Mod) % Mod);
                                    tmp %= Mod;
                                    cur[k]++;
                                    tmp *= ((count[h] - cur[h] + Mod) % Mod);
                                    tmp %= Mod;
                                    cur[h]++;
                                    tmp *= ((count[g] - cur[g] + Mod) % Mod);
                                    tmp %= Mod;
                                    cur[g]++;
                                    tmp *= ((count[u] - cur[u] + Mod) % Mod);
                                    tmp %= Mod;
                                    cur[u]++;
                                    tmp *= ((count[l] - cur[l] + Mod) % Mod);
                                    tmp %= Mod;
                                    cur[l]++;
                                    // tmp *= 720;
                                    tmp %= Mod;
                                    int start = 6;
                                    for(int y = 0; y <= m; y++){
                                        if(cur[y] > 0){
                                            tmp *= c[start][(int)cur[y]];
                                          // System.out.println(start + " " + cur[y] + " " + c[start][(int)cur[y]]);
                                            tmp %= Mod;
                                            start -= cur[y];
                                        }
                                    }
                                    result += tmp;
                                    result %=Mod;
                                }
                            }
                        }
                    }
                }
            }
        }
        out.println(result);
        out.close();
    }

    static int cal(int index, int smaller, int greater, int left, String v) {
        if (left < 0) {
            return 0;
        }
        if (index == v.length()) {
            if (left == 0) {
                if (greater == 1) {
                    return 1;
                }
                return 0;
            }
            return 0;
        }
        if (dp[index][smaller][greater][left] != -1) {
            return dp[index][smaller][greater][left];
        }
        int result = 0;
        int cur = v.charAt(index) - '0';
        for (int i = 0; i < 10; i++) {
            if (i > cur) {
                if (smaller == 1) {
                    result += cal(index + 1, smaller, i > 0 ? 1 : greater, left - ((i == 4 || i == 7) ? 1 : 0), v);
                }
            } else {
                result += cal(index + 1, i < cur ? 1 : smaller, i > 0 ? 1 : greater, left - ((i == 4 || i == 7) ? 1 : 0), v);
            }
        }
        return dp[index][smaller][greater][left] = result;
    }

    static long squareDist(int x, int y) {
        long X = x;
        long Y = y;
        return X * X + Y * Y;
    }

    static int find(int index, int[] u) {
        if (index != u[index]) {
            return u[index] = find(u[index], u);
        }
        return index;
    }

    public static long pow(int a, int b, long mod) {
        if (b == 0) {
            return 1;
        }
        if (b == 1) {
            return a;
        }
        long v = pow(a, b / 2, mod);
        if (b % 2 == 0) {
            return (v * v) % mod;
        } else {
            return (((v * v) % mod) * a) % mod;
        }
    }

    public static int[][] powSquareMatrix(int[][] A, long p) {
        int[][] unit = new int[A.length][A.length];
        for (int i = 0; i < unit.length; i++) {
            unit[i][i] = 1;
        }
        if (p == 0) {
            return unit;
        }
        int[][] val = powSquareMatrix(A, p / 2);
        if (p % 2 == 0) {
            return mulMatrix(val, val);
        } else {
            return mulMatrix(A, mulMatrix(val, val));
        }

    }

    public static int[][] mulMatrix(int[][] A, int[][] B) {
        int[][] result = new int[A.length][B[0].length];
        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result[0].length; j++) {
                long temp = 0;
                for (int k = 0; k < A[0].length; k++) {

                    temp += ((long) A[i][k] * B[k][j] % Mod);
                    temp %= Mod;
                }
                temp %= Mod;
                result[i][j] = (int) temp;
            }
        }

        return result;
    }

    public static boolean nextPer(int[] data) {
        int i = data.length - 1;
        while (i > 0 && data[i] < data[i - 1]) {
            i--;
        }
        if (i == 0) {
            return false;
        }
        int j = data.length - 1;
        while (data[j] < data[i - 1]) {
            j--;
        }
        int temp = data[i - 1];
        data[i - 1] = data[j];
        data[j] = temp;
        Arrays.sort(data, i, data.length);
        return true;




    }

    static class FT {

        int[] data;

        FT(int n) {
            data = new int[n];
        }

        void update(int index, int val) {
            // System.out.println("UPDATE INDEX " + index);
            while (index < data.length) {
                data[index] += val;
                index += index & (-index);

                //    System.out.println("NEXT " +index);
            }
        }

        int get(int index) {
            //  System.out.println("GET INDEX " + index);
            int result = 0;
            while (index > 0) {
                result += data[index];
                index -= index & (-index);
                // System.out.println("BACK " + index);
            }
            return result;
        }
    }

    static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }

    static long pow(long a, int b) {
        if (b == 0) {
            return 1;
        }
        if (b == 1) {
            return a;
        }
        long val = pow(a, b / 2);
        if (b % 2 == 0) {

            return val * val % Mod;
        } else {
            return (val * val % Mod) * a % Mod;
        }
    }

//    static Point intersect(Point a, Point b, Point c) {
//        double D = cross(a, b);
//        if (D != 0) {
//            return new Point(cross(c, b) / D, cross(a, c) / D);
//        }
//        return null;
//    }
//
//    static Point convert(Point a, double angle) {
//        double x = a.x * cos(angle) - a.y * sin(angle);
//        double y = a.x * sin(angle) + a.y * cos(angle);
//        return new Point(x, y);
//    }
    static Point minus(Point a, Point b) {
        return new Point(a.x - b.x, a.y - b.y);
    }
//
//    static Point add(Point a, Point b) {
//        return new Point(a.x + b.x, a.y + b.y);
//    }
//

    /**
     * Cross product ab*ac
     *
     * @param a
     * @param b
     * @param c
     * @return
     */
    static double cross(Point a, Point b, Point c) {
        Point ab = new Point(b.x - a.x, b.y - a.y);
        Point ac = new Point(c.x - a.x, c.y - a.y);
        return cross(ab, ac);
    }

    static double cross(Point a, Point b) {
        return a.x * b.y - a.y * b.x;
    }

    /**
     * Dot product ab*ac;
     *
     * @param a
     * @param b
     * @param c
     * @return
     */
    static long dot(Point a, Point b, Point c) {
        Point ab = new Point(b.x - a.x, b.y - a.y);
        Point ac = new Point(c.x - a.x, c.y - a.y);
        return dot(ab, ac);
    }

    static long dot(Point a, Point b) {
        long total = a.x * b.x;
        total += a.y * b.y;
        return total;
    }

    static double dist(Point a, Point b) {
        long total = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
        return Math.sqrt(total);
    }

    static long norm(Point a) {
        long result = a.x * a.x;
        result += a.y * a.y;
        return result;
    }

    static double dist(Point a, Point b, Point x, boolean isSegment) {
        double dist = cross(a, b, x) / dist(a, b);
        // System.out.println("DIST " + dist);

        if (isSegment) {
            Point ab = new Point(b.x - a.x, b.y - a.y);

            long dot1 = dot(a, b, x);
            long norm = norm(ab);
            double u = (double) dot1 / norm;
            if (u < 0) {
                return dist(a, x);
            }

            if (u > 1) {
                return dist(b, x);
            }
        }
        return Math.abs(dist);




    }

    static long squareDist(Point a, Point b) {
        long x = a.x - b.x;
        long y = a.y - b.y;
        return x * x + y * y;
    }

    static class Point {

        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return "Point{" + "x=" + x + ", y=" + y + '}';
        }
    }

    static class Scanner {

        BufferedReader br;
        StringTokenizer st;

        public Scanner() throws FileNotFoundException {
            //System.setOut(new PrintStream(new BufferedOutputStream(System.out), true));
            br = new BufferedReader(new InputStreamReader(System.in));
            //br = new BufferedReader(new FileReader(new File("A-large (2).in")));
        }

        public String next() {


            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    throw new RuntimeException();
                }
            }
            return st.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public String nextLine() {
            st = null;
            try {
                return br.readLine();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }

        public boolean endLine() {
            try {
                String next = br.readLine();
                while (next != null && next.trim().isEmpty()) {
                    next = br.readLine();
                }
                if (next == null) {
                    return true;
                }
                st = new StringTokenizer(next);
                return st.hasMoreTokens();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }
    }
}