L. Limited Increasing Sequences
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Krystalova is studying a very particular sequence that she likes very much. Krystalova named the sequence: "Limited Increasing Sequence". A sequence $$$X$$$ of positive integer numbers is a limited increasing sequence if and only if every element $$$X_i$$$ is not greater than the sum of all the items $$$X_j$$$ $$$|$$$ $$$j \lt i$$$. In other words, every element $$$X_i$$$ meets the following condition:

$$$$$$\sum_{j=1}^{i-1}X_{j} \geq X_{i}$$$$$$

Let $$$f(X)$$$ be the sum of all the elements in a limited increasing sequence, it is said the limited increasing sequence $$$X$$$ produces $$$K$$$ if $$$f(X) = K$$$.

Looking at this sequence, Krystalova found that a number $$$K$$$ may be produced as the result of different $$$X$$$. She wants to know how many different limited increasing sequences produces $$$K$$$.

Help Krystalova to solve her problem!

Input

In the first line, you will have a single integer $$$K$$$ ($$$1 \leq K \leq 10^6$$$)

Output

Print a line with a single number with the result. As the answer might be very large, please output the answer modulo $$$10^9 + 7$$$

Examples
Input
10
Output
84
Input
2022
Output
904964280
Input
3
Output
1