P409185 - GYM103451 E One more splitting problem - SSOJ

Memory Limit：256 MB Time Limit：1 S

Judge Style：Text Compare Creator：

Submit：0 Solved：0

上一题 Submit 下一题 Submit Record Statistics MD

E. One more splitting problemtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard 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 < 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$$$.

ExamplesInput

Output

Input

Output

Krosh Kaliningrad Contest 2

409185: GYM103451 E One more splitting problem

Description

Source/Category

加入题单