某不科学的多重等比求和¶
预估时间限制：0.5 秒。内存限制：128 MB。
实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。
背景故事¶
小A在做学园都市第零次高中模拟考试试卷时，发现了一道有意思的数学题，于是他决定结合算法知识进行数据范围加强。
形式化问题描述¶
给定正整数 \(n,m,a\) .定义
\[
F_0(x)=\sum_{i=x}^{2x}a^i,\qquad F_t(x)=\sum_{y=1}^{x}F_{t-1}(y)\quad(t\ge1,x\ge1).
\]
求 \(F_m(n)\bmod2147483647\) 的非负最小剩余。所有求和均包含两个端点。
输入格式¶
一行三个整数 \(n,m,a\) .
输出格式¶
输出一行一个整数，范围为 \([0,2147483646]\) .
样例¶
样例 1¶
输入¶
3 2 2
输出¶
194
样例 2¶
输入¶
3 2 1
输出¶
16
样例 3¶
输入¶
1 1000000 7
输出¶
56
样例解释¶
第一组的初始值为 \(6,28,120\) ，第一轮得到 \(6,34,154\) ，第二轮第三项为 \(194\) .第二组初始值为 \(2,3,4\) ，两轮后第三项为 \(16\) .第三组只涉及第一个位置，任意轮数后都等于 \(7+49=56\) .
数据范围与保证¶
\(1\le n,a\le2\times10^9\) ，\(1\le m\le10^6\) .
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |