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 maxn = 1e6 + 10;
const long long mod = 1e9 + 7;
int n, part[30], Part[2][30], lg, a[30], b[2][30];
long long dp[30][2], Dp[2][30][2], ans;
void Round_1() {
  dp[lg + 1][0] = 1;
  for (int y = 1; y <= n; y++) {
    for (int x = lg; x > -1; x--) {
      dp[x][y & 1] = (dp[x + 1][1 - (y & 1)] * a[x] +
                      dp[x][1 - (y & 1)] * (part[lg] - part[x - 1] - y + 1)) %
                     mod;
    }
    if (y == 1) dp[lg + 1][0] = 0;
  }
  ans = dp[0][n & 1];
}
void Round_2() {
  if ((1 << (lg - 1)) * 3 > n) return;
  Dp[1][lg][0] = 1;
  for (int y = 1; y <= n; y++) {
    for (int x = 0; x <= lg - 1; x++) {
      int z = y & 1;
      Dp[1][x][z] =
          (Dp[1][x + 1][1 - z] * b[1][x] +
           Dp[1][x][1 - z] * (Part[1][lg - 1] - Part[1][x - 1] - y + 1)) %
          mod;
      Dp[0][x][z] =
          (Dp[1][x][1 - z] * (Part[0][lg - 1] - Part[0][x - 1]) +
           Dp[0][x + 1][1 - z] * (b[1][x] + b[0][x]) +
           Dp[0][x][1 - z] * (Part[0][lg - 1] + Part[1][lg - 1] -
                              Part[0][x - 1] - Part[1][x - 1] - y + 1)) %
          mod;
    }
    if (y == 1) Dp[1][lg][0] = 0;
  }
  ans = (ans + Dp[0][0][n & 1]) % mod;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int y = 0; y <= 20; y++) {
    if ((1 << y) <= n) lg = y;
  }
  for (int y = 1; y <= n; y++) {
    int i = y;
    int po = 0;
    while (!(i & 1)) i >>= 1, po++;
    a[po]++;
    b[(y % 3 == 0)][min(lg - 1, po)]++;
  }
  part[0] = a[0];
  Part[0][0] = b[0][0], Part[1][0] = b[1][0];
  for (int y = 1; y <= lg; y++)
    part[y] = part[y - 1] + a[y], Part[0][y] = Part[0][y - 1] + b[0][y],
    Part[1][y] = Part[1][y - 1] + b[1][y];
  Round_1();
  Round_2();
  cout << ans;
  return 0;
}
