题目描述
Problem Background
The problem setter is too inexperienced to come up with anything more challenging.
Problem Description
DLS is a boy who enjoys playing games.
Today, he saw $N$ weapons from a friend, where the power value of the $i$-th weapon is $i$.
He has observed these $N$ weapons for a long time and plans to buy some of them. He wants to use the power values of the purchased weapons to form any power value, where the power values of the weapons can be added together or subtracted.
For example, a weapon with a power value of $3$ can form power values like $\dots, -6, -3, 0, 3, 6, \dots$.
He wants to find all the schemes that satisfy the above conditions, but the number of schemes is too large. Can you help him calculate it?
The answer should be taken modulo $10^9 + 7$.
Input and Output Format
Input Format
A single line containing an integer $N$.
Output Format
A single line containing an integer representing the answer.
Sample Input and Output
Sample Input #1
5
Sample Output #1
26
Sample Input #2
16
Sample Output #2
65243
Notes
| Data Percentage | Constraint |
|---|---|
| $10\%$ | $N \le 20$ |
| $30\%$ | $N \le 2000$ |
| $60\%$ | $N \le 10^7$ |
| $100\%$ | $N \le 10^{11}$ |
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分