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.
import java.io.*;
import java.util.*;

public class Codeforces1174E {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int mod = 1000000007;
		
		int nFact = 1;
		for (int i = 2; i <= n; i++) {
			nFact = multiply(nFact, i, mod);
		}
		
		int ntemp = n;
		int k = 0;
		while (ntemp > 0) {
			ntemp /= 2;
			k++;
		}
		
		int[] val = new int[k];
		for (int i = 0; i < k; i++) {
			val[i] = 1 << (k-1-i);
		}
		int[] a = new int[k];
		for (int i = 0; i < k; i++) {
			a[i] = n/(val[i]);
		}
		for (int i = k-1; i > 0; i--) {
			a[i] -= a[i-1];
		}
		
		int ans = nFact;
		int partialSum = 0;
		for (int i = k-1; i >= 0; i--) {
			partialSum += a[i];
			ans = multiply(ans, multiply(a[i], inverse(partialSum, mod), mod), mod);
		}
		
		if (n >= (3*val[0])/2) {
			for (int rep = 0; rep < (k-1); rep++) {
				val[rep] = (3*val[rep])/2;
				
				for (int i = 0; i < k; i++) {
					a[i] = n/(val[i]);
				}
				for (int i = k-1; i > 0; i--) {
					a[i] -= a[i-1];
				}
				
				int ans2 = nFact;
				partialSum = 0;
				for (int i = k-1; i >= 0; i--) {
					partialSum += a[i];
					ans2 = multiply(ans2, multiply(a[i], inverse(partialSum, mod), mod), mod);
				}
				
				ans = (ans+ans2)%mod;
			}
		}
		
		System.out.println(ans);
	}
	
	public static int multiply (int a, int b, int n) {
		long ab = (long) a * (long) b;
		return ((int) (ab%n));
	}
	
	public static int inverse (int a, int n) {
		int m = n;
		int r1 = 1;
		int r2 = 0;
		int r3 = 0;
		int r4 = 1;
		while ((a > 0) && (n > 0)) {
			if (n >= a) {
				r3 -= r1*(n/a);
				r4 -= r2*(n/a);
				n = n%a;
			}
			else {
				int tmp = a;
				a = n;
				n = tmp;
				tmp = r1;
				r1 = r3;
				r3 = tmp;
				tmp = r2;
				r2 = r4;
				r4 = tmp;
			}
		}
		if (a == 0) {
			if (r3 >= 0)
				return (r3%m);
			else
				return (m+(r3%m));
		}
		else {
			if (r1 >= 0)
				return (r1%m);
			else
				return (m+(r1%m));
		}

	}
}
