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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(
    (unsigned int)chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
std::ostream& operator<<(std::ostream& stream, const vector<T>& vec) {
  for (T x : vec) stream << x << ' ';
  return stream;
}
template <typename T>
std::istream& operator>>(std::istream& stream, vector<T>& vec) {
  for (T& x : vec) stream >> x;
  return stream;
}
template <typename T, typename U>
std::ostream& operator<<(std::ostream& stream, const pair<T, U>& pr) {
  stream << pr.first << ' ' << pr.second;
  return stream;
}
template <typename T, typename U>
std::istream& operator>>(std::istream& stream, pair<T, U>& pr) {
  stream >> pr.first >> pr.second;
  return stream;
}
template <typename T>
void operator+=(vector<T>& vec, const T value) {
  for (T& x : vec) x += value;
}
template <typename T>
void operator-=(vector<T>& vec, const T value) {
  for (T& x : vec) x -= value;
}
template <typename T>
void operator++(vector<T>& vec) {
  vec += 1;
}
template <typename T>
void operator++(vector<T>& vec, T) {
  vec += 1;
}
template <typename T>
void operator--(vector<T>& vec) {
  vec -= 1;
}
template <typename T>
void operator--(vector<T>& vec, T) {
  vec -= 1;
}
template <typename T>
void operator*=(vector<T>& vec, const T value) {
  for (T& x : vec) x *= value;
}
template <typename T>
void operator/=(vector<T>& vec, const T value) {
  for (T& x : vec) x /= value;
}
template <typename T, typename U>
void operator+=(pair<T, U>& vec, const T value) {
  vec.first += value;
  vec.second += value;
}
template <typename T, typename U>
void operator-=(pair<T, U>& vec, const T value) {
  vec.first -= value;
  vec.second -= value;
}
template <typename T, typename U>
void operator++(pair<T, U>& vec) {
  vec += 1;
}
template <typename T, typename U>
void operator++(pair<T, U>& vec, T) {
  vec += 1;
}
template <typename T, typename U>
void operator--(pair<T, U>& vec) {
  vec -= 1;
}
template <typename T, typename U>
void operator--(pair<T, U>& vec, T) {
  vec -= 1;
}
template <typename T, typename U>
void operator*=(pair<T, U>& vec, const T value) {
  vec.first *= value;
  vec.second *= value;
}
template <typename T, typename U>
void operator/=(pair<T, U>& vec, const T value) {
  vec.first /= value;
  vec.second /= value;
}
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) { return '"' + s + '"'; }
string to_string(char c) {
  string s;
  s += c;
  return s;
}
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "1" : "0"); }
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
template <class T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
void bharo(int N_N) { return; }
template <typename Head, typename... Tail>
void bharo(int N_N, Head& H, Tail&... T) {
  H.resize(N_N);
  bharo(N_N, T...);
}
void safai() { return; }
template <typename Head, typename... Tail>
void safai(Head& H, Tail&... T) {
  H.clear();
  safai(T...);
}
template <typename T>
T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a;
    swap(a, m);
    u -= t * v;
    swap(u, v);
  }
  assert(m == 1);
  return u;
}
template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;
  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }
  template <typename U>
  static Type normalize(const U& x) {
    Type v;
    if (-mod() <= x && x < mod())
      v = static_cast<Type>(x);
    else
      v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }
  const Type& operator()() const { return value; }
  template <typename U>
  explicit operator U() const {
    return static_cast<U>(value);
  }
  constexpr static Type mod() { return T::value; }
  Modular& operator+=(const Modular& other) {
    if ((value += other.value) >= mod()) value -= mod();
    return *this;
  }
  Modular& operator-=(const Modular& other) {
    if ((value -= other.value) < 0) value += mod();
    return *this;
  }
  template <typename U>
  Modular& operator+=(const U& other) {
    return *this += Modular(other);
  }
  template <typename U>
  Modular& operator-=(const U& other) {
    return *this -= Modular(other);
  }
  Modular& operator++() { return *this += 1; }
  Modular& operator--() { return *this -= 1; }
  Modular operator++(int) {
    Modular result(*this);
    *this += 1;
    return result;
  }
  Modular operator--(int) {
    Modular result(*this);
    *this -= 1;
    return result;
  }
  Modular operator-() const { return Modular(-value); }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    value = normalize(static_cast<int64_t>(value) *
                      static_cast<int64_t>(rhs.value));
    return *this;
  }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, long long>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    long long q = static_cast<long long>(static_cast<long double>(value) *
                                         rhs.value / mod());
    value = normalize(value * rhs.value - q * mod());
    return *this;
  }
  template <typename U = T>
  typename enable_if<!is_integral<typename Modular<U>::Type>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    value = normalize(value * rhs.value);
    return *this;
  }
  Modular& operator/=(const Modular& other) {
    return *this *= Modular(inverse(other.value, mod()));
  }
  friend const Type& abs(const Modular& x) { return x.value; }
  template <typename U>
  friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);
  template <typename U>
  friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);
  template <typename V, typename U>
  friend V& operator>>(V& stream, Modular<U>& number);

 private:
  Type value;
};
template <typename T>
bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) {
  return lhs.value == rhs.value;
}
template <typename T, typename U>
bool operator==(const Modular<T>& lhs, U rhs) {
  return lhs == Modular<T>(rhs);
}
template <typename T, typename U>
bool operator==(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) == rhs;
}
template <typename T>
bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(const Modular<T>& lhs, U rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(U lhs, const Modular<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T>
bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) {
  return lhs.value < rhs.value;
}
template <typename T>
Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T>
Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T>
Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T>
Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
  assert(b >= 0);
  Modular<T> x = a, res = 1;
  U p = b;
  while (p > 0) {
    if (p & 1) res *= x;
    x *= x;
    p >>= 1;
  }
  return res;
}
template <typename T>
bool IsZero(const Modular<T>& number) {
  return number() == 0;
}
template <typename T>
string to_string(const Modular<T>& number) {
  return to_string(number());
}
template <typename U, typename T>
U& operator<<(U& stream, const Modular<T>& number) {
  return stream << number();
}
template <typename U, typename T>
U& operator>>(U& stream, Modular<T>& number) {
  typename common_type<typename Modular<T>::Type, long long>::type x;
  stream >> x;
  number.value = Modular<T>::normalize(x);
  return stream;
}
constexpr int md = (int)1e9 + 7;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
const long long int mod = 1e9 + 7;
Mint C(int n, int k) {
  Mint res = 1;
  if (k > n - k) k = n - k;
  for (int i = 0; i < k; ++i) {
    res *= (n - i);
    res /= (i + 1);
  }
  return res;
}
Mint find(int tot, int d) {
  if (d < 0 || d > tot) return 0;
  Mint ans = C(tot, d);
  ans *= power((Mint)2, d);
  ans *= power((Mint)8, (tot - d));
  return ans;
}
Mint tell(int x, int D) {
  int old = D;
  string s = to_string(x);
  int n = s.size();
  if (D > n || D < 0) return 0;
  Mint ans = 0;
  int tot = n;
  for (int i = 0; i < n; i++) {
    tot--;
    int d = s[i] - '0';
    if (tot == 0) {
      if (d == 0) break;
      int can = d, ext = 0;
      if (d > 4) {
        can--;
        ext++;
      }
      if (d > 7) {
        can--;
        ext++;
      }
      if (D == 1) ans += ext;
      if (D == 0) ans += can;
      break;
    }
    if (d <= 4)
      ans += d * find(tot, D);
    else if (d <= 7)
      ans += (d - 1) * find(tot, D) + find(tot, D - 1);
    else
      ans += (d - 2) * find(tot, D) + 2 * find(tot, D - 1);
    D -= d == 4;
    D -= d == 7;
    if (D < 0) break;
  }
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    cnt += (s[i] == '4') || (s[i] == '7');
  }
  if (cnt == old) {
    ans++;
  }
  if (old == 0) ans--;
  return ans;
}
vector<Mint> all(14);
Mint solve(int x) {
  vector<int> a(6);
  Mint ans = 0;
  for (a[0] = 0; a[0] < x; a[0]++) {
    for (a[1] = 0; a[0] + a[1] < x; a[1]++)
      for (a[2] = 0; a[0] + a[1] + a[2] < x; a[2]++)
        for (a[3] = 0; a[0] + a[1] + a[2] + a[3] < x; a[3]++)
          for (a[4] = 0; a[0] + a[1] + a[2] + a[3] + a[4] < x; a[4]++)
            for (a[5] = 0; a[0] + a[1] + a[2] + a[3] + a[4] + a[5] < x;
                 a[5]++) {
              auto here = all;
              Mint temp = 1;
              for (int i = 0; i < 6; i++) {
                if (here[a[i]] == 0) {
                  temp = 0;
                  break;
                }
                temp *= here[a[i]];
                here[a[i]]--;
              }
              ans += temp;
            }
  }
  return ans;
}
void testcase() {
  int m;
  cin >> m;
  int dig = to_string(m).size();
  for (int i = 0; i <= dig; i++) {
    all[i] = tell(m, i);
  }
  Mint ans = 0;
  for (int i = 1; i <= dig; i++) {
    ans += all[i] * solve(i);
  }
  cout << ans << '\n';
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt = 1;
  while (tt--) {
    testcase();
  }
  return 0;
}