E. One more splitting problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given number $$$n$$$. Find number of ways to decompose number $$$n$$$ on summands where each next summand is at least twice more than the previous. So for each $$$1 \le i \lt k$$$ where $$$k$$$ is number of summands $$$a_{i + 1} \ge 2 * a_i$$$.

Input

You are given number $$$1 \le n \le 3 * 10^5$$$.

Output

Output answer modulo $$$10^9+7$$$.

Examples
Input
10
Output
6
Input
6
Output
3