#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:36777216")
template <class T>
inline T &RD(T &);
template <class T>
inline void OT(const T &);
inline long long RD() {
  long long x;
  return RD(x);
}
inline char &RC(char &c) {
  scanf(" %c", &c);
  return c;
}
inline char RC() {
  char c;
  return RC(c);
}
inline double &RF(double &x) {
  scanf("%lf", &x);
  return x;
}
inline double RF() {
  double x;
  return RF(x);
}
inline char *RS(char *s) {
  scanf("%s", s);
  return s;
}
template <class T0, class T1>
inline T0 &RD(T0 &x0, T1 &x1) {
  RD(x0), RD(x1);
  return x0;
}
template <class T0, class T1, class T2>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2) {
  RD(x0), RD(x1), RD(x2);
  return x0;
}
template <class T0, class T1, class T2, class T3>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3) {
  RD(x0), RD(x1), RD(x2), RD(x3);
  return x0;
}
template <class T0, class T1, class T2, class T3, class T4>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4) {
  RD(x0), RD(x1), RD(x2), RD(x3), RD(x4);
  return x0;
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5) {
  RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5);
  return x0;
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6) {
  RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6);
  return x0;
}
template <class T0, class T1>
inline void OT(const T0 &x0, const T1 &x1) {
  OT(x0), OT(x1);
}
template <class T0, class T1, class T2>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2) {
  OT(x0), OT(x1), OT(x2);
}
template <class T0, class T1, class T2, class T3>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3) {
  OT(x0), OT(x1), OT(x2), OT(x3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3,
               const T4 &x4) {
  OT(x0), OT(x1), OT(x2), OT(x3), OT(x4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3,
               const T4 &x4, const T5 &x5) {
  OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3,
               const T4 &x4, const T5 &x5, const T6 &x6) {
  OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6);
}
inline char &RC(char &a, char &b) {
  RC(a), RC(b);
  return a;
}
inline char &RC(char &a, char &b, char &c) {
  RC(a), RC(b), RC(c);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d) {
  RC(a), RC(b), RC(c), RC(d);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d, char &e) {
  RC(a), RC(b), RC(c), RC(d), RC(e);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d, char &e, char &f) {
  RC(a), RC(b), RC(c), RC(d), RC(e), RC(f);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d, char &e, char &f, char &g) {
  RC(a), RC(b), RC(c), RC(d), RC(e), RC(f), RC(g);
  return a;
}
inline double &RF(double &a, double &b) {
  RF(a), RF(b);
  return a;
}
inline double &RF(double &a, double &b, double &c) {
  RF(a), RF(b), RF(c);
  return a;
}
inline double &RF(double &a, double &b, double &c, double &d) {
  RF(a), RF(b), RF(c), RF(d);
  return a;
}
inline double &RF(double &a, double &b, double &c, double &d, double &e) {
  RF(a), RF(b), RF(c), RF(d), RF(e);
  return a;
}
inline double &RF(double &a, double &b, double &c, double &d, double &e,
                  double &f) {
  RF(a), RF(b), RF(c), RF(d), RF(e), RF(f);
  return a;
}
inline double &RF(double &a, double &b, double &c, double &d, double &e,
                  double &f, double &g) {
  RF(a), RF(b), RF(c), RF(d), RF(e), RF(f), RF(g);
  return a;
}
inline void RS(char *s1, char *s2) { RS(s1), RS(s2); }
inline void RS(char *s1, char *s2, char *s3) { RS(s1), RS(s2), RS(s3); }
template <class T>
inline void RST(T &A) {
  memset(A, 0, sizeof(A));
}
template <class T0, class T1>
inline void RST(T0 &A0, T1 &A1) {
  RST(A0), RST(A1);
}
template <class T0, class T1, class T2>
inline void RST(T0 &A0, T1 &A1, T2 &A2) {
  RST(A0), RST(A1), RST(A2);
}
template <class T0, class T1, class T2, class T3>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3) {
  RST(A0), RST(A1), RST(A2), RST(A3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4) {
  RST(A0), RST(A1), RST(A2), RST(A3), RST(A4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5) {
  RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6) {
  RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6);
}
template <class T>
inline void FLC(T &A, int x) {
  memset(A, x, sizeof(A));
}
template <class T0, class T1>
inline void FLC(T0 &A0, T1 &A1, int x) {
  FLC(A0, x), FLC(A1, x);
}
template <class T0, class T1, class T2>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x);
}
template <class T0, class T1, class T2, class T3>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x),
      FLC(A6, x);
}
template <class T>
inline void CLR(priority_queue<T, vector<T>, less<T> > &Q) {
  while (!Q.empty()) Q.pop();
}
template <class T>
inline void CLR(priority_queue<T, vector<T>, greater<T> > &Q) {
  while (!Q.empty()) Q.pop();
}
template <class T>
inline void CLR(T &A) {
  A.clear();
}
template <class T0, class T1>
inline void CLR(T0 &A0, T1 &A1) {
  CLR(A0), CLR(A1);
}
template <class T0, class T1, class T2>
inline void CLR(T0 &A0, T1 &A1, T2 &A2) {
  CLR(A0), CLR(A1), CLR(A2);
}
template <class T0, class T1, class T2, class T3>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5), CLR(A6);
}
template <class T>
inline void CLR(T &A, int n) {
  for (int i = 0; i < int(n); ++i) CLR(A[i]);
}
template <class T>
inline T &SRT(T &A) {
  sort(A.begin(), A.end());
  return A;
}
template <class T, class C>
inline T &SRT(T &A, C B) {
  sort(A.begin(), A.end(), B);
  return A;
}
const int dx4[] = {-1, 0, 1, 0};
const int dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const int dy8[] = {0, 1, 0, -1, -1, 1, -1, 1};
const int dxhorse[] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int dyhorse[] = {1, -1, 2, -2, 2, -2, 1, -1};
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const long long INFF = 1LL << 60;
const double EPS = 1e-9;
const double OO = 1e15;
const double PI = acos(-1.0);
template <class T>
inline void checkMin(T &a, const T b) {
  if (b < a) a = b;
}
template <class T>
inline void checkMax(T &a, const T b) {
  if (a < b) a = b;
}
template <class T>
inline void checkMin(T &a, T &b, const T x) {
  checkMin(a, x), checkMin(b, x);
}
template <class T>
inline void checkMax(T &a, T &b, const T x) {
  checkMax(a, x), checkMax(b, x);
}
template <class T, class C>
inline void checkMin(T &a, const T b, C c) {
  if (c(b, a)) a = b;
}
template <class T, class C>
inline void checkMax(T &a, const T b, C c) {
  if (c(a, b)) a = b;
}
template <class T>
inline T min(T a, T b, T c) {
  return min(min(a, b), c);
}
template <class T>
inline T max(T a, T b, T c) {
  return max(max(a, b), c);
}
template <class T>
inline T min(T a, T b, T c, T d) {
  return min(min(a, b), min(c, d));
}
template <class T>
inline T max(T a, T b, T c, T d) {
  return max(max(a, b), max(c, d));
}
template <class T>
inline T sqr(T a) {
  return a * a;
}
template <class T>
inline T cub(T a) {
  return a * a * a;
}
inline int Ceil(int x, int y) { return (x - 1) / y + 1; }
namespace BO {
inline bool _1(int x, int i) { return bool(x & 1 << i); }
inline bool _1(long long x, int i) { return bool(x & 1LL << i); }
inline long long _1(int i) { return 1LL << i; }
inline long long _U(int i) { return _1(i) - 1; };
inline int reverse_bits(int x) {
  x = ((x >> 1) & 0x55555555) | ((x << 1) & 0xaaaaaaaa);
  x = ((x >> 2) & 0x33333333) | ((x << 2) & 0xcccccccc);
  x = ((x >> 4) & 0x0f0f0f0f) | ((x << 4) & 0xf0f0f0f0);
  x = ((x >> 8) & 0x00ff00ff) | ((x << 8) & 0xff00ff00);
  x = ((x >> 16) & 0x0000ffff) | ((x << 16) & 0xffff0000);
  return x;
}
inline long long reverse_bits(long long x) {
  x = ((x >> 1) & 0x5555555555555555LL) | ((x << 1) & 0xaaaaaaaaaaaaaaaaLL);
  x = ((x >> 2) & 0x3333333333333333LL) | ((x << 2) & 0xccccccccccccccccLL);
  x = ((x >> 4) & 0x0f0f0f0f0f0f0f0fLL) | ((x << 4) & 0xf0f0f0f0f0f0f0f0LL);
  x = ((x >> 8) & 0x00ff00ff00ff00ffLL) | ((x << 8) & 0xff00ff00ff00ff00LL);
  x = ((x >> 16) & 0x0000ffff0000ffffLL) | ((x << 16) & 0xffff0000ffff0000LL);
  x = ((x >> 32) & 0x00000000ffffffffLL) | ((x << 32) & 0xffffffff00000000LL);
  return x;
}
template <class T>
inline bool odd(T x) {
  return x & 1;
}
template <class T>
inline T low_bit(T x) {
  return x & -x;
}
template <class T>
inline T high_bit(T x) {
  T p = low_bit(x);
  while (p != x) x -= p, p = low_bit(x);
  return p;
}
template <class T>
inline T cover_bit(T x) {
  T p = 1;
  while (p < x) p <<= 1;
  return p;
}
inline int low_idx(int x) { return __builtin_ffs(x); }
inline int low_idx(long long x) { return __builtin_ffsll(x); }
inline int high_idx(int x) { return low_idx(reverse_bits(x)); }
inline int high_idx(long long x) { return low_idx(reverse_bits(x)); }
inline int clz(int x) { return __builtin_clz(x); }
inline int clz(long long x) { return __builtin_clzll(x); }
inline int ctz(int x) { return __builtin_ctz(x); }
inline int ctz(long long x) { return __builtin_ctzll(x); }
inline int parity(int x) { return __builtin_parity(x); }
inline int parity(long long x) { return __builtin_parityll(x); }
inline int lg2(int a) { return 31 - __builtin_clz(a); }
inline int count_bits(int x) { return __builtin_popcount(x); }
inline int count_bits(long long x) { return __builtin_popcountll(x); }
};  // namespace BO
namespace NT {
inline void INC(int &a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
}
inline int sum(int a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  return a;
}
inline void DEC(int &a, int b) {
  a -= b;
  if (a < 0) a += MOD;
}
inline int dff(int a, int b) {
  a -= b;
  if (a < 0) a += MOD;
  return a;
}
inline void MUL(int &a, int b) { a = (long long)a * b % MOD; }
inline int pdt(int a, int b) { return (long long)a * b % MOD; }
inline int sum(int a, int b, int c) { return sum(sum(a, b), c); }
inline int sum(int a, int b, int c, int d) { return sum(sum(a, b), sum(c, d)); }
inline int pdt(int a, int b, int c) { return pdt(pdt(a, b), c); }
inline int pdt(int a, int b, int c, int d) { return pdt(pdt(pdt(a, b), c), d); }
inline int pow(int a, long long b) {
  int c(1);
  while (b) {
    if (b & 1) MUL(c, a);
    MUL(a, a), b >>= 1;
  }
  return c;
}
template <class T>
inline T pow(T a, long long b) {
  T c(1);
  while (b) {
    if (b & 1) c *= a;
    a *= a, b >>= 1;
  }
  return c;
}
inline int _I(int b) {
  int a = MOD, x1 = 0, x2 = 1, q;
  while (true) {
    q = a / b, a %= b;
    if (!a) return (x2 + MOD) % MOD;
    DEC(x1, pdt(q, x2));
    q = b / a, b %= a;
    if (!b) return (x1 + MOD) % MOD;
    DEC(x2, pdt(q, x1));
  }
}
inline void DIA(int &a, int b) { MUL(a, _I(b)); }
inline int qtt(int a, int b) { return pdt(a, _I(b)); }
inline int phi(int n) {
  int res = n;
  for (int i = 2; sqr(i) <= n; ++i)
    if (!(n % i)) {
      DEC(res, qtt(res, i));
      do {
        n /= i;
      } while (!(n % i));
    }
  if (n != 1) DEC(res, qtt(res, n));
  return res;
}
template <class T>
T GCD(T a, T b) {
  return b ? GCD(b, a % b) : a;
}
template <class T>
T extendGCD(T a, T b, T &x, T &y) {
  if (!b) return x = 1, y = 0, a;
  T res = extendGCD(b, a % b, x, y), tmp = x;
  x = y, y = tmp - (a / b) * y;
  return res;
}
template <class T>
inline T inv(T w, T M) {
  if (M <= 0) return -1;
  T x, y, d;
  d = extendGCD(w, M, x, y);
  if (d != 1) return -1;
  x = ((x % M) + M) % M;
  return x;
}
};  // namespace NT
namespace RNG {
inline unsigned int rand16() { return (bool(rand() & 1) << 15) | rand(); }
inline unsigned int rand32() { return (rand16() << 16) | rand16(); }
inline unsigned long long rand64() {
  return ((long long)rand32() << 32) | rand32();
}
inline unsigned long long random(long long l, long long r) {
  return rand64() % (r - l) + l;
}
int dice() { return rand() % 6; }
bool coin() { return bool(rand() % 2); }
};  // namespace RNG
namespace CLOCK {
double s0, s1, rd, k, T;
inline double getTime() { return 1.0 * clock() / CLOCKS_PER_SEC; }
inline void st0(double _T = 0.98) { T = _T, s0 = getTime(); }
inline void st1(double _k = 1.618) { k = _k, s1 = getTime(); }
inline void ed1() { rd = getTime() - s1; }
inline double elapsed() { return getTime() - s0; }
inline bool safe() { return elapsed() + rd * k < T; }
}  // namespace CLOCK
template <class T>
pair<T, T> operator+(const pair<T, T> &p1, const pair<T, T> &p2) {
  return pair<T, T>(p1.first + p2.first, p1.second + p2.second);
}
template <class T>
pair<T, T> operator-(const pair<T, T> &p1, const pair<T, T> &p2) {
  return pair<T, T>(p1.first - p2.first, p1.second - p2.second);
}
template <class T>
pair<T, T> operator*(const pair<T, T> &lhs, T k) {
  return pair<T, T>(lhs.first * k, lhs.second * k);
}
namespace Math {
long long GCD(long long a, long long b) { return b ? GCD(b, a % b) : a; }
long long extendGCD(long long a, long long b, long long &x, long long &y) {
  if (!b) return x = 1, y = 0, a;
  long long res = extendGCD(b, a % b, x, y), tmp = x;
  x = y, y = tmp - (a / b) * y;
  return res;
}
long long power(long long x, long long k) {
  long long res = 1;
  while (k) {
    if (k & 1) res *= x;
    x *= x, k >>= 1;
  }
  return res;
}
long long powerMod(long long x, long long k, long long m) {
  long long res = 1;
  while (x %= m, k) {
    if (k & 1) res *= x, res %= m;
    x *= x, k >>= 1;
  }
  return res;
}
long long inverse(long long a, long long p, long long t = 1) {
  long long pt = power(p, t);
  long long x, y;
  y = extendGCD(a, pt, x, y);
  return x < 0 ? x += pt : x;
}
long long linearCongruence(long long a, long long b, long long p, long long q) {
  long long x, y;
  y = extendGCD(p, q, x, y);
  while (b < a) b += q / y;
  x *= b - a, x = p * x + a, x %= p * q;
  if (x < 0) x += p * q;
  return x;
}
const int PRIMERANGE = 1000000;
int prime[PRIMERANGE + 1];
int getPrime() {
  memset(prime, 0, sizeof(int) * (PRIMERANGE + 1));
  for (int i = 2; i <= PRIMERANGE; i++) {
    if (!prime[i]) prime[++prime[0]] = i;
    for (int j = 1; j <= prime[0] && prime[j] <= PRIMERANGE / i; j++) {
      prime[prime[j] * i] = 1;
      if (i % prime[j] == 0) break;
    }
  }
  return prime[0];
}
int factor[100][3], facCnt;
int getFactors(int x) {
  facCnt = 0;
  int tmp = x;
  for (int i = 1; prime[i] <= tmp / prime[i]; i++) {
    factor[facCnt][1] = 1, factor[facCnt][2] = 0;
    if (tmp % prime[i] == 0) factor[facCnt][0] = prime[i];
    while (tmp % prime[i] == 0)
      factor[facCnt][2]++, factor[facCnt][1] *= prime[i], tmp /= prime[i];
    if (factor[facCnt][1] > 1) facCnt++;
  }
  if (tmp != 1)
    factor[facCnt][0] = tmp, factor[facCnt][1] = tmp, factor[facCnt++][2] = 1;
  return facCnt;
}
long long combinationModP(long long n, long long k, long long p) {
  if (k > n) return 0;
  if (n - k < k) k = n - k;
  long long a = 1, b = 1, x, y;
  int pcnt = 0;
  for (int i = 1; i <= k; i++) {
    x = n - i + 1, y = i;
    while (x % p == 0) x /= p, pcnt++;
    while (y % p == 0) y /= p, pcnt--;
    x %= p, y %= p, a *= x, b *= y;
    b %= p, a %= p;
  }
  if (pcnt) return 0;
  extendGCD(b, p, x, y);
  if (x < 0) x += p;
  a *= x, a %= p;
  return a;
}
};  // namespace Math
namespace Geo {
const double eps = 1e-8;
int dblcmp(double d) {
  if (fabs(d) < eps) return 0;
  return d > eps ? 1 : -1;
}
int sgn(double a) { return a < -eps ? -1 : a > eps; }
inline double sqr(double x) { return x * x; }
struct Point2D {
  double x, y;
  Point2D() {}
  Point2D(double _x, double _y) : x(_x), y(_y){};
  void input() { scanf("%lf%lf", &x, &y); }
  void output() { printf("%.2f %.2f\n", x, y); }
  bool operator==(Point2D a) const {
    return dblcmp(a.x - x) == 0 && dblcmp(a.y - y) == 0;
  }
  bool operator<(Point2D a) const {
    return dblcmp(a.x - x) == 0 ? dblcmp(y - a.y) < 0 : x < a.x;
  }
  double len() { return hypot(x, y); }
  double len2() { return x * x + y * y; }
  Point2D operator+(const Point2D &A) const {
    return Point2D(x + A.x, y + A.y);
  }
  Point2D operator-(const Point2D &A) const {
    return Point2D(x - A.x, y - A.y);
  }
  Point2D operator*(const double _x) const { return Point2D(x * _x, y * _x); }
  double operator*(const Point2D &A) const { return x * A.x + y * A.y; }
  double operator^(const Point2D &A) const { return x * A.y - y * A.x; }
  Point2D operator/(const double _p) const { return Point2D(x / _p, y / _p); }
  double distance(Point2D p) { return hypot(x - p.x, y - p.y); }
  Point2D add(Point2D p) { return Point2D(x + p.x, y + p.y); }
  Point2D sub(Point2D p) { return Point2D(x - p.x, y - p.y); }
  Point2D mul(double b) { return Point2D(x * b, y * b); }
  Point2D div(double b) { return Point2D(x / b, y / b); }
  double dot(Point2D p) { return x * p.x + y * p.y; }
  double det(Point2D p) { return x * p.y - y * p.x; }
  double rad(Point2D a, Point2D b) {
    Point2D p = *this;
    return fabs(atan2(fabs(a.sub(p).det(b.sub(p))), a.sub(p).dot(b.sub(p))));
  }
  Point2D trunc(double r) {
    double l = len();
    if (!dblcmp(l)) return *this;
    r /= l;
    return Point2D(x * r, y * r);
  }
  Point2D rotleft() { return Point2D(-y, x); }
  Point2D rotright() { return Point2D(y, -x); }
  Point2D rotate(Point2D p, double angle) {
    Point2D v = this->sub(p);
    double c = cos(angle), s = sin(angle);
    return Point2D(p.x + v.x * c - v.y * s, p.y + v.x * s + v.y * c);
  }
};
double cross(Point2D a, Point2D b, Point2D c) {
  return (b.sub(a)).det(c.sub(a));
}
}  // namespace Geo
using namespace Geo;
template <class T>
inline T &RD(T &x) {
  char c;
  for (c = getchar(); c < '0'; c = getchar())
    ;
  x = c - '0';
  for (c = getchar(); '0' <= c && c <= '9'; c = getchar()) x = x * 10 + c - '0';
  return x;
}
int ____Case;
template <class T>
inline void OT(const T &x) {
  printf("%d\n", x);
}
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
unsigned long long dp[15][15];
void DP() {
  memset(dp, 0, sizeof(dp));
  dp[0][0] = 1;
  for (int i = 0; i < 10; i++) {
    for (int j = 0; j <= i; j++) {
      if (dp[i][j] == 0) continue;
      dp[i + 1][j + 1] += dp[i][j] * 2;
      dp[i + 1][j] += dp[i][j] * 8;
    }
  }
}
int slove(int n, int m) {
  int bit[20], len = 0;
  while (n) {
    bit[len++] = n % 10;
    n /= 10;
  }
  int cnt = 0, tot = 0;
  for (int i = len - 1; i >= 0; i--) {
    for (int j = 0; j < bit[i]; j++) {
      if (j == 4 || j == 7) {
        if (tot != m) cnt += dp[i][m - tot - 1];
      } else
        cnt += dp[i][m - tot];
    }
    if (bit[i] == 4 || bit[i] == 7) tot++;
    if (tot > m) break;
  }
  if (tot == m) cnt++;
  if (m == 0) cnt--;
  return cnt;
}
int n;
int cnt[10], t[10];
unsigned long long ans = 0;
void dfs(int idx, int now, int limit, unsigned long long ret) {
  if (idx == 6) {
    ans = (ans + ret) % 1000000007;
    return;
  }
  for (int i = 0; i < 10; i++) {
    if (i + now >= limit) break;
    if (t[i] == 0) continue;
    t[i]--;
    dfs(idx + 1, now + i, limit, ret * (t[i] + 1) % 1000000007);
    t[i]++;
  }
}
int main() {
  DP();
  while (scanf("%d", &n) != EOF) {
    for (int i = 0; i < 10; i++) {
      cnt[i] = slove(n, i);
    }
    ans = 0;
    for (int i = 1; i < 10; i++) {
      if (cnt[i] == 0) continue;
      memcpy(t, cnt, sizeof(cnt));
      t[i]--;
      dfs(0, 0, i, cnt[i] % 1000000007);
    }
    printf("%I64d\n", ans);
  }
  return 0;
}

### Prompt

Your challenge is to write a CPP solution to the following 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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:36777216")
template <class T>
inline T &RD(T &);
template <class T>
inline void OT(const T &);
inline long long RD() {
  long long x;
  return RD(x);
}
inline char &RC(char &c) {
  scanf(" %c", &c);
  return c;
}
inline char RC() {
  char c;
  return RC(c);
}
inline double &RF(double &x) {
  scanf("%lf", &x);
  return x;
}
inline double RF() {
  double x;
  return RF(x);
}
inline char *RS(char *s) {
  scanf("%s", s);
  return s;
}
template <class T0, class T1>
inline T0 &RD(T0 &x0, T1 &x1) {
  RD(x0), RD(x1);
  return x0;
}
template <class T0, class T1, class T2>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2) {
  RD(x0), RD(x1), RD(x2);
  return x0;
}
template <class T0, class T1, class T2, class T3>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3) {
  RD(x0), RD(x1), RD(x2), RD(x3);
  return x0;
}
template <class T0, class T1, class T2, class T3, class T4>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4) {
  RD(x0), RD(x1), RD(x2), RD(x3), RD(x4);
  return x0;
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5) {
  RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5);
  return x0;
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6) {
  RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6);
  return x0;
}
template <class T0, class T1>
inline void OT(const T0 &x0, const T1 &x1) {
  OT(x0), OT(x1);
}
template <class T0, class T1, class T2>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2) {
  OT(x0), OT(x1), OT(x2);
}
template <class T0, class T1, class T2, class T3>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3) {
  OT(x0), OT(x1), OT(x2), OT(x3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3,
               const T4 &x4) {
  OT(x0), OT(x1), OT(x2), OT(x3), OT(x4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3,
               const T4 &x4, const T5 &x5) {
  OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3,
               const T4 &x4, const T5 &x5, const T6 &x6) {
  OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6);
}
inline char &RC(char &a, char &b) {
  RC(a), RC(b);
  return a;
}
inline char &RC(char &a, char &b, char &c) {
  RC(a), RC(b), RC(c);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d) {
  RC(a), RC(b), RC(c), RC(d);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d, char &e) {
  RC(a), RC(b), RC(c), RC(d), RC(e);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d, char &e, char &f) {
  RC(a), RC(b), RC(c), RC(d), RC(e), RC(f);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d, char &e, char &f, char &g) {
  RC(a), RC(b), RC(c), RC(d), RC(e), RC(f), RC(g);
  return a;
}
inline double &RF(double &a, double &b) {
  RF(a), RF(b);
  return a;
}
inline double &RF(double &a, double &b, double &c) {
  RF(a), RF(b), RF(c);
  return a;
}
inline double &RF(double &a, double &b, double &c, double &d) {
  RF(a), RF(b), RF(c), RF(d);
  return a;
}
inline double &RF(double &a, double &b, double &c, double &d, double &e) {
  RF(a), RF(b), RF(c), RF(d), RF(e);
  return a;
}
inline double &RF(double &a, double &b, double &c, double &d, double &e,
                  double &f) {
  RF(a), RF(b), RF(c), RF(d), RF(e), RF(f);
  return a;
}
inline double &RF(double &a, double &b, double &c, double &d, double &e,
                  double &f, double &g) {
  RF(a), RF(b), RF(c), RF(d), RF(e), RF(f), RF(g);
  return a;
}
inline void RS(char *s1, char *s2) { RS(s1), RS(s2); }
inline void RS(char *s1, char *s2, char *s3) { RS(s1), RS(s2), RS(s3); }
template <class T>
inline void RST(T &A) {
  memset(A, 0, sizeof(A));
}
template <class T0, class T1>
inline void RST(T0 &A0, T1 &A1) {
  RST(A0), RST(A1);
}
template <class T0, class T1, class T2>
inline void RST(T0 &A0, T1 &A1, T2 &A2) {
  RST(A0), RST(A1), RST(A2);
}
template <class T0, class T1, class T2, class T3>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3) {
  RST(A0), RST(A1), RST(A2), RST(A3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4) {
  RST(A0), RST(A1), RST(A2), RST(A3), RST(A4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5) {
  RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6) {
  RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6);
}
template <class T>
inline void FLC(T &A, int x) {
  memset(A, x, sizeof(A));
}
template <class T0, class T1>
inline void FLC(T0 &A0, T1 &A1, int x) {
  FLC(A0, x), FLC(A1, x);
}
template <class T0, class T1, class T2>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x);
}
template <class T0, class T1, class T2, class T3>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x),
      FLC(A6, x);
}
template <class T>
inline void CLR(priority_queue<T, vector<T>, less<T> > &Q) {
  while (!Q.empty()) Q.pop();
}
template <class T>
inline void CLR(priority_queue<T, vector<T>, greater<T> > &Q) {
  while (!Q.empty()) Q.pop();
}
template <class T>
inline void CLR(T &A) {
  A.clear();
}
template <class T0, class T1>
inline void CLR(T0 &A0, T1 &A1) {
  CLR(A0), CLR(A1);
}
template <class T0, class T1, class T2>
inline void CLR(T0 &A0, T1 &A1, T2 &A2) {
  CLR(A0), CLR(A1), CLR(A2);
}
template <class T0, class T1, class T2, class T3>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5), CLR(A6);
}
template <class T>
inline void CLR(T &A, int n) {
  for (int i = 0; i < int(n); ++i) CLR(A[i]);
}
template <class T>
inline T &SRT(T &A) {
  sort(A.begin(), A.end());
  return A;
}
template <class T, class C>
inline T &SRT(T &A, C B) {
  sort(A.begin(), A.end(), B);
  return A;
}
const int dx4[] = {-1, 0, 1, 0};
const int dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const int dy8[] = {0, 1, 0, -1, -1, 1, -1, 1};
const int dxhorse[] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int dyhorse[] = {1, -1, 2, -2, 2, -2, 1, -1};
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const long long INFF = 1LL << 60;
const double EPS = 1e-9;
const double OO = 1e15;
const double PI = acos(-1.0);
template <class T>
inline void checkMin(T &a, const T b) {
  if (b < a) a = b;
}
template <class T>
inline void checkMax(T &a, const T b) {
  if (a < b) a = b;
}
template <class T>
inline void checkMin(T &a, T &b, const T x) {
  checkMin(a, x), checkMin(b, x);
}
template <class T>
inline void checkMax(T &a, T &b, const T x) {
  checkMax(a, x), checkMax(b, x);
}
template <class T, class C>
inline void checkMin(T &a, const T b, C c) {
  if (c(b, a)) a = b;
}
template <class T, class C>
inline void checkMax(T &a, const T b, C c) {
  if (c(a, b)) a = b;
}
template <class T>
inline T min(T a, T b, T c) {
  return min(min(a, b), c);
}
template <class T>
inline T max(T a, T b, T c) {
  return max(max(a, b), c);
}
template <class T>
inline T min(T a, T b, T c, T d) {
  return min(min(a, b), min(c, d));
}
template <class T>
inline T max(T a, T b, T c, T d) {
  return max(max(a, b), max(c, d));
}
template <class T>
inline T sqr(T a) {
  return a * a;
}
template <class T>
inline T cub(T a) {
  return a * a * a;
}
inline int Ceil(int x, int y) { return (x - 1) / y + 1; }
namespace BO {
inline bool _1(int x, int i) { return bool(x & 1 << i); }
inline bool _1(long long x, int i) { return bool(x & 1LL << i); }
inline long long _1(int i) { return 1LL << i; }
inline long long _U(int i) { return _1(i) - 1; };
inline int reverse_bits(int x) {
  x = ((x >> 1) & 0x55555555) | ((x << 1) & 0xaaaaaaaa);
  x = ((x >> 2) & 0x33333333) | ((x << 2) & 0xcccccccc);
  x = ((x >> 4) & 0x0f0f0f0f) | ((x << 4) & 0xf0f0f0f0);
  x = ((x >> 8) & 0x00ff00ff) | ((x << 8) & 0xff00ff00);
  x = ((x >> 16) & 0x0000ffff) | ((x << 16) & 0xffff0000);
  return x;
}
inline long long reverse_bits(long long x) {
  x = ((x >> 1) & 0x5555555555555555LL) | ((x << 1) & 0xaaaaaaaaaaaaaaaaLL);
  x = ((x >> 2) & 0x3333333333333333LL) | ((x << 2) & 0xccccccccccccccccLL);
  x = ((x >> 4) & 0x0f0f0f0f0f0f0f0fLL) | ((x << 4) & 0xf0f0f0f0f0f0f0f0LL);
  x = ((x >> 8) & 0x00ff00ff00ff00ffLL) | ((x << 8) & 0xff00ff00ff00ff00LL);
  x = ((x >> 16) & 0x0000ffff0000ffffLL) | ((x << 16) & 0xffff0000ffff0000LL);
  x = ((x >> 32) & 0x00000000ffffffffLL) | ((x << 32) & 0xffffffff00000000LL);
  return x;
}
template <class T>
inline bool odd(T x) {
  return x & 1;
}
template <class T>
inline T low_bit(T x) {
  return x & -x;
}
template <class T>
inline T high_bit(T x) {
  T p = low_bit(x);
  while (p != x) x -= p, p = low_bit(x);
  return p;
}
template <class T>
inline T cover_bit(T x) {
  T p = 1;
  while (p < x) p <<= 1;
  return p;
}
inline int low_idx(int x) { return __builtin_ffs(x); }
inline int low_idx(long long x) { return __builtin_ffsll(x); }
inline int high_idx(int x) { return low_idx(reverse_bits(x)); }
inline int high_idx(long long x) { return low_idx(reverse_bits(x)); }
inline int clz(int x) { return __builtin_clz(x); }
inline int clz(long long x) { return __builtin_clzll(x); }
inline int ctz(int x) { return __builtin_ctz(x); }
inline int ctz(long long x) { return __builtin_ctzll(x); }
inline int parity(int x) { return __builtin_parity(x); }
inline int parity(long long x) { return __builtin_parityll(x); }
inline int lg2(int a) { return 31 - __builtin_clz(a); }
inline int count_bits(int x) { return __builtin_popcount(x); }
inline int count_bits(long long x) { return __builtin_popcountll(x); }
};  // namespace BO
namespace NT {
inline void INC(int &a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
}
inline int sum(int a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  return a;
}
inline void DEC(int &a, int b) {
  a -= b;
  if (a < 0) a += MOD;
}
inline int dff(int a, int b) {
  a -= b;
  if (a < 0) a += MOD;
  return a;
}
inline void MUL(int &a, int b) { a = (long long)a * b % MOD; }
inline int pdt(int a, int b) { return (long long)a * b % MOD; }
inline int sum(int a, int b, int c) { return sum(sum(a, b), c); }
inline int sum(int a, int b, int c, int d) { return sum(sum(a, b), sum(c, d)); }
inline int pdt(int a, int b, int c) { return pdt(pdt(a, b), c); }
inline int pdt(int a, int b, int c, int d) { return pdt(pdt(pdt(a, b), c), d); }
inline int pow(int a, long long b) {
  int c(1);
  while (b) {
    if (b & 1) MUL(c, a);
    MUL(a, a), b >>= 1;
  }
  return c;
}
template <class T>
inline T pow(T a, long long b) {
  T c(1);
  while (b) {
    if (b & 1) c *= a;
    a *= a, b >>= 1;
  }
  return c;
}
inline int _I(int b) {
  int a = MOD, x1 = 0, x2 = 1, q;
  while (true) {
    q = a / b, a %= b;
    if (!a) return (x2 + MOD) % MOD;
    DEC(x1, pdt(q, x2));
    q = b / a, b %= a;
    if (!b) return (x1 + MOD) % MOD;
    DEC(x2, pdt(q, x1));
  }
}
inline void DIA(int &a, int b) { MUL(a, _I(b)); }
inline int qtt(int a, int b) { return pdt(a, _I(b)); }
inline int phi(int n) {
  int res = n;
  for (int i = 2; sqr(i) <= n; ++i)
    if (!(n % i)) {
      DEC(res, qtt(res, i));
      do {
        n /= i;
      } while (!(n % i));
    }
  if (n != 1) DEC(res, qtt(res, n));
  return res;
}
template <class T>
T GCD(T a, T b) {
  return b ? GCD(b, a % b) : a;
}
template <class T>
T extendGCD(T a, T b, T &x, T &y) {
  if (!b) return x = 1, y = 0, a;
  T res = extendGCD(b, a % b, x, y), tmp = x;
  x = y, y = tmp - (a / b) * y;
  return res;
}
template <class T>
inline T inv(T w, T M) {
  if (M <= 0) return -1;
  T x, y, d;
  d = extendGCD(w, M, x, y);
  if (d != 1) return -1;
  x = ((x % M) + M) % M;
  return x;
}
};  // namespace NT
namespace RNG {
inline unsigned int rand16() { return (bool(rand() & 1) << 15) | rand(); }
inline unsigned int rand32() { return (rand16() << 16) | rand16(); }
inline unsigned long long rand64() {
  return ((long long)rand32() << 32) | rand32();
}
inline unsigned long long random(long long l, long long r) {
  return rand64() % (r - l) + l;
}
int dice() { return rand() % 6; }
bool coin() { return bool(rand() % 2); }
};  // namespace RNG
namespace CLOCK {
double s0, s1, rd, k, T;
inline double getTime() { return 1.0 * clock() / CLOCKS_PER_SEC; }
inline void st0(double _T = 0.98) { T = _T, s0 = getTime(); }
inline void st1(double _k = 1.618) { k = _k, s1 = getTime(); }
inline void ed1() { rd = getTime() - s1; }
inline double elapsed() { return getTime() - s0; }
inline bool safe() { return elapsed() + rd * k < T; }
}  // namespace CLOCK
template <class T>
pair<T, T> operator+(const pair<T, T> &p1, const pair<T, T> &p2) {
  return pair<T, T>(p1.first + p2.first, p1.second + p2.second);
}
template <class T>
pair<T, T> operator-(const pair<T, T> &p1, const pair<T, T> &p2) {
  return pair<T, T>(p1.first - p2.first, p1.second - p2.second);
}
template <class T>
pair<T, T> operator*(const pair<T, T> &lhs, T k) {
  return pair<T, T>(lhs.first * k, lhs.second * k);
}
namespace Math {
long long GCD(long long a, long long b) { return b ? GCD(b, a % b) : a; }
long long extendGCD(long long a, long long b, long long &x, long long &y) {
  if (!b) return x = 1, y = 0, a;
  long long res = extendGCD(b, a % b, x, y), tmp = x;
  x = y, y = tmp - (a / b) * y;
  return res;
}
long long power(long long x, long long k) {
  long long res = 1;
  while (k) {
    if (k & 1) res *= x;
    x *= x, k >>= 1;
  }
  return res;
}
long long powerMod(long long x, long long k, long long m) {
  long long res = 1;
  while (x %= m, k) {
    if (k & 1) res *= x, res %= m;
    x *= x, k >>= 1;
  }
  return res;
}
long long inverse(long long a, long long p, long long t = 1) {
  long long pt = power(p, t);
  long long x, y;
  y = extendGCD(a, pt, x, y);
  return x < 0 ? x += pt : x;
}
long long linearCongruence(long long a, long long b, long long p, long long q) {
  long long x, y;
  y = extendGCD(p, q, x, y);
  while (b < a) b += q / y;
  x *= b - a, x = p * x + a, x %= p * q;
  if (x < 0) x += p * q;
  return x;
}
const int PRIMERANGE = 1000000;
int prime[PRIMERANGE + 1];
int getPrime() {
  memset(prime, 0, sizeof(int) * (PRIMERANGE + 1));
  for (int i = 2; i <= PRIMERANGE; i++) {
    if (!prime[i]) prime[++prime[0]] = i;
    for (int j = 1; j <= prime[0] && prime[j] <= PRIMERANGE / i; j++) {
      prime[prime[j] * i] = 1;
      if (i % prime[j] == 0) break;
    }
  }
  return prime[0];
}
int factor[100][3], facCnt;
int getFactors(int x) {
  facCnt = 0;
  int tmp = x;
  for (int i = 1; prime[i] <= tmp / prime[i]; i++) {
    factor[facCnt][1] = 1, factor[facCnt][2] = 0;
    if (tmp % prime[i] == 0) factor[facCnt][0] = prime[i];
    while (tmp % prime[i] == 0)
      factor[facCnt][2]++, factor[facCnt][1] *= prime[i], tmp /= prime[i];
    if (factor[facCnt][1] > 1) facCnt++;
  }
  if (tmp != 1)
    factor[facCnt][0] = tmp, factor[facCnt][1] = tmp, factor[facCnt++][2] = 1;
  return facCnt;
}
long long combinationModP(long long n, long long k, long long p) {
  if (k > n) return 0;
  if (n - k < k) k = n - k;
  long long a = 1, b = 1, x, y;
  int pcnt = 0;
  for (int i = 1; i <= k; i++) {
    x = n - i + 1, y = i;
    while (x % p == 0) x /= p, pcnt++;
    while (y % p == 0) y /= p, pcnt--;
    x %= p, y %= p, a *= x, b *= y;
    b %= p, a %= p;
  }
  if (pcnt) return 0;
  extendGCD(b, p, x, y);
  if (x < 0) x += p;
  a *= x, a %= p;
  return a;
}
};  // namespace Math
namespace Geo {
const double eps = 1e-8;
int dblcmp(double d) {
  if (fabs(d) < eps) return 0;
  return d > eps ? 1 : -1;
}
int sgn(double a) { return a < -eps ? -1 : a > eps; }
inline double sqr(double x) { return x * x; }
struct Point2D {
  double x, y;
  Point2D() {}
  Point2D(double _x, double _y) : x(_x), y(_y){};
  void input() { scanf("%lf%lf", &x, &y); }
  void output() { printf("%.2f %.2f\n", x, y); }
  bool operator==(Point2D a) const {
    return dblcmp(a.x - x) == 0 && dblcmp(a.y - y) == 0;
  }
  bool operator<(Point2D a) const {
    return dblcmp(a.x - x) == 0 ? dblcmp(y - a.y) < 0 : x < a.x;
  }
  double len() { return hypot(x, y); }
  double len2() { return x * x + y * y; }
  Point2D operator+(const Point2D &A) const {
    return Point2D(x + A.x, y + A.y);
  }
  Point2D operator-(const Point2D &A) const {
    return Point2D(x - A.x, y - A.y);
  }
  Point2D operator*(const double _x) const { return Point2D(x * _x, y * _x); }
  double operator*(const Point2D &A) const { return x * A.x + y * A.y; }
  double operator^(const Point2D &A) const { return x * A.y - y * A.x; }
  Point2D operator/(const double _p) const { return Point2D(x / _p, y / _p); }
  double distance(Point2D p) { return hypot(x - p.x, y - p.y); }
  Point2D add(Point2D p) { return Point2D(x + p.x, y + p.y); }
  Point2D sub(Point2D p) { return Point2D(x - p.x, y - p.y); }
  Point2D mul(double b) { return Point2D(x * b, y * b); }
  Point2D div(double b) { return Point2D(x / b, y / b); }
  double dot(Point2D p) { return x * p.x + y * p.y; }
  double det(Point2D p) { return x * p.y - y * p.x; }
  double rad(Point2D a, Point2D b) {
    Point2D p = *this;
    return fabs(atan2(fabs(a.sub(p).det(b.sub(p))), a.sub(p).dot(b.sub(p))));
  }
  Point2D trunc(double r) {
    double l = len();
    if (!dblcmp(l)) return *this;
    r /= l;
    return Point2D(x * r, y * r);
  }
  Point2D rotleft() { return Point2D(-y, x); }
  Point2D rotright() { return Point2D(y, -x); }
  Point2D rotate(Point2D p, double angle) {
    Point2D v = this->sub(p);
    double c = cos(angle), s = sin(angle);
    return Point2D(p.x + v.x * c - v.y * s, p.y + v.x * s + v.y * c);
  }
};
double cross(Point2D a, Point2D b, Point2D c) {
  return (b.sub(a)).det(c.sub(a));
}
}  // namespace Geo
using namespace Geo;
template <class T>
inline T &RD(T &x) {
  char c;
  for (c = getchar(); c < '0'; c = getchar())
    ;
  x = c - '0';
  for (c = getchar(); '0' <= c && c <= '9'; c = getchar()) x = x * 10 + c - '0';
  return x;
}
int ____Case;
template <class T>
inline void OT(const T &x) {
  printf("%d\n", x);
}
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
unsigned long long dp[15][15];
void DP() {
  memset(dp, 0, sizeof(dp));
  dp[0][0] = 1;
  for (int i = 0; i < 10; i++) {
    for (int j = 0; j <= i; j++) {
      if (dp[i][j] == 0) continue;
      dp[i + 1][j + 1] += dp[i][j] * 2;
      dp[i + 1][j] += dp[i][j] * 8;
    }
  }
}
int slove(int n, int m) {
  int bit[20], len = 0;
  while (n) {
    bit[len++] = n % 10;
    n /= 10;
  }
  int cnt = 0, tot = 0;
  for (int i = len - 1; i >= 0; i--) {
    for (int j = 0; j < bit[i]; j++) {
      if (j == 4 || j == 7) {
        if (tot != m) cnt += dp[i][m - tot - 1];
      } else
        cnt += dp[i][m - tot];
    }
    if (bit[i] == 4 || bit[i] == 7) tot++;
    if (tot > m) break;
  }
  if (tot == m) cnt++;
  if (m == 0) cnt--;
  return cnt;
}
int n;
int cnt[10], t[10];
unsigned long long ans = 0;
void dfs(int idx, int now, int limit, unsigned long long ret) {
  if (idx == 6) {
    ans = (ans + ret) % 1000000007;
    return;
  }
  for (int i = 0; i < 10; i++) {
    if (i + now >= limit) break;
    if (t[i] == 0) continue;
    t[i]--;
    dfs(idx + 1, now + i, limit, ret * (t[i] + 1) % 1000000007);
    t[i]++;
  }
}
int main() {
  DP();
  while (scanf("%d", &n) != EOF) {
    for (int i = 0; i < 10; i++) {
      cnt[i] = slove(n, i);
    }
    ans = 0;
    for (int i = 1; i < 10; i++) {
      if (cnt[i] == 0) continue;
      memcpy(t, cnt, sizeof(cnt));
      t[i]--;
      dfs(0, 0, i, cnt[i] % 1000000007);
    }
    printf("%I64d\n", ans);
  }
  return 0;
}

```