Background

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

Problem Description

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$.

Input Format

One line with one integer $N$.

Output Format

One line with one integer, representing the answer.

5

26

16

65243

Hint

Translated by ChatGPT 5