# 某不科学的多重等比求和

预估时间限制：0.5 秒。内存限制：128 MB。

实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

小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

### 输入

```text
3 2 2
```

### 输出

```text
194
```

### 样例 2

### 输入

```text
3 2 1
```

### 输出

```text
16
```

### 样例 3

### 输入

```text
1 1000000 7
```

### 输出

```text
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% | 无额外条件 |