Codeforces Round 563 (Div. 2) |
---|
Finished |
Let's define a function $$$f(p)$$$ on a permutation $$$p$$$ as follows. Let $$$g_i$$$ be the greatest common divisor (GCD) 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$$$.
The only line contains the integer $$$n$$$ ($$$2 \le n \le 10^6$$$) — the length of the permutations.
The only line should contain your answer modulo $$$10^9+7$$$.
2
1
3
4
6
120
Consider the second example: these are the permutations of length $$$3$$$:
The maximum value $$$f_{max}(3) = 2$$$, and there are $$$4$$$ permutations $$$p$$$ such that $$$f(p)=2$$$.
Name |
---|