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:
/**
 * Created by Aminul on 11/12/2018.
 */

import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class CF258B {
    public static void main(String[] args)throws Exception {
        FastReader in = new FastReader(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        dp = new int[2][11][11];
        int n = in.nextInt();
        arr = makeDigitArray(n);
        cnt = new int[11];
        for (int i = 0; i <= arr.length; i++) {
            for(int x[][] : dp) for(int y[] : x) Arrays.fill(y, -1);
            cnt[i] = calcEqual(0, 0, i);
        }
        cnt[0]--;
        long ans = 0;
        for (int i = 1; i <= arr.length; i++) {
            ans = (ans + cnt[i] * count(6, i - 1)) % mod;
        }
        pw.println(ans);
        pw.close();
    }

    static int[] makeDigitArray(int n) {
        String s = String.valueOf(n);
        int a[] = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            a[i] = s.charAt(i) - '0';
        }
        return a;
    }

    static long mod = (long)1e9+7;

    static int boolToInt(boolean b){
        return b ? 1 : 0;
    }
    static int arr[], cnt[];
    static int dp[][][];
    static int calcEqual(int isSmall, int pos, int k) {
        if(k < 0) return 0;
        if(pos == arr.length) {
            return k == 0 ? 1 : 0;
        }
        if(dp[isSmall][k][pos] != -1) return dp[isSmall][k][pos];
        int ans = 0;
        for (int i = 0; i <= 9; i++) {
            if(isSmall == 0 && i > arr[pos]) break;
            ans += calcEqual(isSmall | boolToInt(i < arr[pos]), pos+1, k - boolToInt(i == 4 || i == 7));
        }
        return dp[isSmall][k][pos] = ans;
    }

    static long count(int left, int num) {
        if (left == 0) {
            return 1;
        }
        long ans = 0;
        for (int i = 0; i <= num; i++) {
            if (cnt[i] > 0) {
                cnt[i]--;
                ans = (ans + (cnt[i] + 1) * count(left - 1, num - i)) % mod;
                cnt[i]++;
            }
        }
        return ans;
    }

    static int brute(int n, int k) {
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            int a[] = makeDigitArray(i);
            int x = 0;
            for(int p : a) {
                if(p == 4 || p == 7) x++;
            }
            if(x == k){
                cnt++;
            }
        }
        return cnt;
    }

    static void debug(Object...obj) {
        System.err.println(Arrays.deepToString(obj));
    }

    static class FastReader {
        InputStream is;
        private byte[] inbuf = new byte[1024];
        private int lenbuf = 0, ptrbuf = 0;

        public FastReader(InputStream is) {
            this.is = is;
        }

        public int readByte() {
            if (lenbuf == -1) throw new InputMismatchException();
            if (ptrbuf >= lenbuf) {
                ptrbuf = 0;
                try {
                    lenbuf = is.read(inbuf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (lenbuf <= 0) return -1;
            }
            return inbuf[ptrbuf++];
        }

        public boolean isSpaceChar(int c) {
            return !(c >= 33 && c <= 126);
        }
        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }

        public int skip() {
            int b;
            while ((b = readByte()) != -1 && isSpaceChar(b)) ;
            return b;
        }

        public String next() {
            int b = skip();
            StringBuilder sb = new StringBuilder();
            while (!(isSpaceChar(b))) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }



        public String nextLine() {
            int c = skip();
            StringBuilder sb = new StringBuilder();
            while (!isEndOfLine(c)){
                sb.appendCodePoint(c);
                c = readByte();
            }
            return sb.toString();
        }

        public int nextInt() {
            int num = 0, b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            while (true) {
                if (b >= '0' && b <= '9') {
                    num = (num << 3) + (num << 1) + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public long nextLong() {
            long num = 0;
            int b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }

            while (true) {
                if (b >= '0' && b <= '9') {
                    num = (num << 3) + (num << 1) + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

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

        public char[] next(int n) {
            char[] buf = new char[n];
            int b = skip(), p = 0;
            while (p < n && !(isSpaceChar(b))) {
                buf[p++] = (char) b;
                b = readByte();
            }
            return n == p ? buf : Arrays.copyOf(buf, p);
        }

        public char readChar() {
            return (char) skip();
        }
    }
}