P5218 Boring Easy Problem II

The problem setter is not skilled, and can only make this kind of problem.

DLS is a boy who likes playing games. Today, he saw $N$ weapons from his friend, where the power value of the $i$-th weapon is $i$. He observed these $N$ weapons for a long time and plans to buy some of them, but he wants to use the power values of the weapons he buys to form any power value. The power values of each weapon can be added together, and can even be subtracted. For example, with a weapon whose power value is $3$, the power values that can be formed are $\dots,-6,-3,0,3,6,\dots$. He wants to find all purchase plans that satisfy the above condition, but there are too many plans. Can you help him compute it? Output the answer modulo $10^9+7$.

One line with one integer $N$.

One line with one integer, representing the answer.

|Percentage of testdata|Constraints| |-|-| |$10\%$|$N \le 20$| |$30\%$|$N \le 2000$| |$60\%$|$N \le 10^7$| |$100\%$|$N \le 10^{11}$| Translated by ChatGPT 5