# 某不科学的多重前缀求和

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

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

## 背景故事

小A在做学园都市第零次高中模拟考试试卷时，发现了一道有意思的数学题，于是他决定结合算法知识进行数据范围加强。

## 形式化问题描述

给定正整数 $n,m$ 、非负整数 $k$ 以及系数 $a_0,\ldots,a_k$ .定义

$$F_0(x)=\sum_{i=0}^{k}a_ix^i$$

对正整数 $t,x$ ，递归定义

$$F_t(x)=\sum_{y=1}^{x}F_{t-1}(y)$$

求 $F_m(n)\bmod2147483647$ 的非负最小剩余。每一层求和都包含端点一和 $x$ .$k=0$ 时初始函数是常数 $a_0$ .

## 输入格式

第一行三个整数 $n,m,k$ .第二行 $k+1$ 个整数，依次为 $a_0,a_1,\ldots,a_k$ .

## 输出格式

输出一行一个整数，表示答案，范围为 $[0,2147483646]$ .

## 样例

### 样例 1

### 输入

```text
3 2 2
1 2 1
```

### 输出

```text
46
```

### 样例 2

### 输入

```text
5 3 0
7
```

### 输出

```text
245
```

### 样例 3

### 输入

```text
1 7 3
1 2 3 4
```

### 输出

```text
10
```

## 样例解释

第一组中，初始前三项为 $4,9,16$ .一轮汇总得到 $4,13,29$ ，第二轮在第三个位置的值为 $4+13+29=46$ .

第二组的初始值恒为七，第二轮前五项为 $7,21,42,70,105$ ，再求和得到 $245$ .第三组只关心第一个位置，任意轮汇总后都保持 $1+2+3+4=10$ .

## 数据范围与保证

对所有数据，$1\le n\le2\times10^9$ ，$1\le m\le10^7$ ，$0\le k\le300$ ，$1\le a_i\le2\times10^9$ .

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |