母亲 Antonija 赚了 $N$ 欧元，并且必须尽快把它们全部花掉。她可以自己留下一部分钱，但剩余的钱必须在几天内平均分配给她的两个儿子。
首先，她选择一个非负整数 $k$ ($0 \le k \le N$) 留给自己。然后，剩余的 $N - k$ 欧元将在 $d$ 天内分配给两个儿子。母亲 Antonija 也可以选择不给儿子分配任何钱，这对应于 $N = k$ 且 $d = 0$ 的情况。
如果分配资金，必须满足每天两个儿子收到的金额相同。如果其中一个儿子在某一天收到 $x$ 欧元，另一个儿子在当天也必须收到 $x$ 欧元，其中 $x$ 必须是一个正整数。总的来说，每个儿子收到的总金额必须相同。
两种分配方案被认为是不同的，如果满足以下至少一个条件：
- 选择留给自己的金额 $k$ 不同
- 分配的天数 $d$ 不同
- 存在至少一天，儿子们收到的金额不同（即每日付款的序列不完全相同）。
你的任务是确定母亲分配资金的不同方案数。由于方案数可能非常大，请输出结果模 $10^9 + 7$ 的值。
输入格式
第一行包含一个自然数 $n$ ($1 \le n \le 10^{18}$)，即题目描述中的数量。
输出格式
输出一个整数，表示母亲 Antonija 分配资金的方案数。
子任务
| 子任务 | 分数 | 数据范围 |
|---|---|---|
| 1 | 12 | $n \le 10$ |
| 2 | 17 | $n \le 1000$ |
| 3 | 36 | $n \le 10^6$ |
| 4 | 5 | 无附加限制。 |
样例
输入样例 1
4
输出样例 1
4
输入样例 2
5
输出样例 2
4
输入样例 3
793
输出样例 3
137435472
说明
样例 1 说明：我们考虑数字 $k$ 的所有可能取值：
- $k = 4 \rightarrow$ 母亲留下了所有的钱，因此唯一的分配方案是儿子们没有收到钱。
- $k = 2 \rightarrow$ 剩余 $2$ 欧元分配给儿子们。唯一合法的分配方案是 $d = 1$，此时每个儿子收到 $1$ 欧元。
- $k = 0 \rightarrow$ 剩余 $4$ 欧元分配给儿子们。有两种合法的分配方案：
- $d = 1 \rightarrow$ 每个儿子收到 $2$ 欧元
- $d = 2 \rightarrow$ 每天每个儿子收到 $1$ 欧元
- $k = 1$ 和 $k = 3 \rightarrow$ 无法分配剩余的金额使得两个儿子每天都能收到相同的正整数金额。
总共有 $1 + 1 + 2 = 4$ 种不同的分配方案。