无聊的水题 II

题目背景

出题人过菜,只会出这种题。

题目描述

DLS 是一个喜欢玩游戏的男生。 今天他从朋友那里看到了 $N$ 件武器,其中第 $i$ 件武器的威力值为$i$。 他观察了这 $N$ 件武器许久,打算买下其中若干件武器,但他想用买下的武器的威力值组合出任意威力值,其中每一件武器已经的威力值可以叠加,甚至可以减去。 例如一个威力值为 $3$ 的武器,可以组合成的威力值为 $\dots,-6,-3,0,3,6,\dots$。 他想找出所有满足以上条件的买下装备的方案,但方案数量实在太多了。你能帮他计算一下吗? 答案对 $10^9+7$ 取模。

输入输出格式

输入格式


一行一个整数 $N$。

输出格式


一行一个整数表示答案

输入输出样例

输入样例 #1

5

输出样例 #1

26

输入样例 #2

16

输出样例 #2

65243

说明

|数据百分比|限制| |-|-| |$10\%$|$N \le 20$| |$30\%$|$N \le 2000$| |$60\%$|$N \le 10^7$| |$100\%$|$N \le 10^{11}$|