P15889 [COCI 2025/2026 #6] 零花钱 / Džeparac

母亲安东尼亚赚了 $N$ 欧元，必须尽快花光所有钱。她可以自己保留一部分钱，但剩余的钱必须在若干天内平均分给她的两个儿子。 首先，她选择一个非负整数 $k$（$0 \le k \le N$）留给自己。剩下的 $N - k$ 欧元将在 $d$ 天内分给两个儿子。母亲也可以选择不给儿子们分钱，这对应于 $N = k$ 且 $d = 0$ 的情况。 如果进行分钱，则每天的分配方式是：两个儿子当天得到相同金额的钱。如果某天一个儿子得到 $x$ 欧元，那么另一个儿子也得到 $x$ 欧元，其中 $x$ 必须是正整数。总的来说，每个儿子获得的总金额必须相同。 两种分配方案被视为不同，当且仅当满足以下条件中的至少一条： - 选择的金额 $k$ 不同； - 天数 $d$ 不同； - 存在至少一天，两个儿子当天获得的金额不同（即每日支付金额的序列不完全相同）。 你的任务是计算母亲可以分配钱的不同方案数。由于方案数可能非常大，请输出结果对 $10^9 + 7$ 取模后的值。

第一行包含一个自然数 $n$（$1 \le n \le 10^{18}$），即题目中所述的金额。

输出一个整数，表示母亲分配钱的不同方案数。

**第一个样例的解释：** 考虑所有可能的 $k$ 值： $k = 4 \to$ 母亲留下所有钱，儿子们没有收到钱，这是一种分配方案。 $k = 2 \to$ 剩余 $2$ 欧元需要分给儿子们。唯一可行的分配是 $d = 1$，即每个儿子得到 $1$ 欧元。 $k = 0 \to$ 剩余 $4$ 欧元需要分给儿子们。存在两种可行的分配方案： $\quad d = 1 \to$ 每个儿子得到 $2$ 欧元； $\quad d = 2 \to$ 每天每个儿子得到 $1$ 欧元。 $k = 1$ 和 $k = 3 \to$ 剩余金额无法分配使得每天每个儿子得到相同正整数金额且两人总金额相同。 总共有 $1 + 1 + 2 = 4$ 种不同的分配方案。 **计分方式** | 子任务 | 分值 | 约束条件 | |:-------:|:------:|--------------------| | 1 | 12 | $n \le 10$ | | 2 | 17 | $n \le 1000$ | | 3 | 36 | $n \le 10^6$ | | 4 | 5 | 无额外限制。 | 翻译由 DeepSeek V3.2 完成