Let's define a function f(p) on a permutation p as follows. Let g_i be the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of elements p_1, p_2, ..., p_i (in other words, it is the GCD of the prefix of length i). Then f(p) is the number of distinct elements among g_1, g_2, ..., g_n.

Let f_{max}(n) be the maximum value of f(p) among all permutations p of integers 1, 2, ..., n.

Given an integers n, count the number of permutations p of integers 1, 2, ..., n, such that f(p) is equal to f_{max}(n). Since the answer may be large, print the remainder of its division by 1000 000 007 = 10^9 + 7.

Input

The only line contains the integer n (2 ≤ n ≤ 10^6) — the length of the permutations.

Output

The only line should contain your answer modulo 10^9+7.

Examples

Input


2


Output


1

Input


3


Output


4

Input


6


Output


120

Note

Consider the second example: these are the permutations of length 3:

  * [1,2,3], f(p)=1. 
  * [1,3,2], f(p)=1. 
  * [2,1,3], f(p)=2. 
  * [2,3,1], f(p)=2. 
  * [3,1,2], f(p)=2. 
  * [3,2,1], f(p)=2. 



The maximum value f_{max}(3) = 2, and there are 4 permutations p such that f(p)=2.
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int n;
int dp[3][25][2][3];
int f(int i, int j, int k, int fst) {
  if (i > n) return 0;
  if (j < 0) return 0;
  if (k < 0) return 0;
  if (i == n) return 1;
  return dp[i & 1][j][k][fst];
}
void solve() {
  cin >> n;
  int len = 0;
  memset(dp, -1, sizeof dp);
  while ((1 << (len + 1)) <= n) len++;
  for (int i = n; i >= 0; i--)
    for (int j = 0; j <= len; j++)
      for (int k = 0; k < 2; k++)
        for (int fst = 0; fst < 3; fst++) {
          if (i >= n) {
            dp[i & 1][j][k][fst] = 1;
            continue;
          }
          if (j < 0) {
            dp[i & 1][j][k][fst] = 0;
            continue;
          }
          if (k < 0) {
            dp[i & 1][j][k][fst] = 0;
            continue;
          }
          if (i == n) {
            dp[i & 1][j][k][fst] = 1;
            continue;
          }
          int opt = n / (1 << (j)) - i;
          int bhag = (1 << j);
          if (k == 1) bhag *= 3;
          opt = n / bhag - i;
          if (fst == 1)
            opt = n / bhag - (n / (bhag * 2));
          else if (fst == 2)
            opt = n / (1 << j) - (n / ((1 << j) * 3));
          if (opt < 0) {
            dp[i & 1][j][k][fst] = 0;
            continue;
          }
          long long x = f(i + 1, j, k, 0);
          long long y = f(i + 1, j - 1, k, 1);
          long long z = f(i + 1, j, k - 1, 2);
          dp[i & 1][j][k][fst] = 1LL * opt * (x + y + z) % MOD;
        }
  long long ans = f(0, len, 0, 1);
  if (n >= ((1 << (len - 1))) * 3) {
    ans += f(0, len - 1, 1, 1);
  }
  ans %= MOD;
  cout << ans << endl;
}
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t = 1;
  while (t--) {
    solve();
  }
  return 0;
}
