# Grox的序列六

- 参考时间限制：0.5 秒。
- 实际时限：标准程序在目标环境的最慢用例中位耗时乘以 2，再按 0.5 秒向上取整。
- 内存限制：128 MB。
- [参考评测环境与测量](../../../docs/评测环境与性能.md)

## 背景故事

> 是先知或神秘主义者为我们带来了电力、抗生素、现代卫生设备、航太科学以及数位计时器吗？绝对不是。是那些循序渐进，利用他人成就创造新奇迹的家伙。
>
> ——科学之书5（《Spore》，[英文资料](https://spore.fandom.com/wiki/Books_of_Science)）

Grox 虽然是一个机械种族，却并非从一开始就是这般模样。经过漫长的进化与自我改造，他们才逐渐成为今天的样子。

为了纪念 Grox 史诗般的进化历程，你决定送给他们一个递推数列作为礼物。这个数列是无穷的，Grox 只会询问其中感兴趣的项；他们也可能调整部分参数，但会保留决定递推结构的关键参数。毕竟，没有人喜欢抄写太长的数字，所有答案都需要按规定取模。

## 形式化问题描述

固定整数 $\beta$ 和非负整数 $k$ .整数参数 $\alpha,a_0,\ldots,a_k$ 定义数列

$$f(0)=\alpha$$

$$f(n)=\beta f(n-1)+\sum_{i=0}^k a_i n^i\qquad(n\ge1)$$

共进行 $Q$ 次操作：

- `0 n` ：询问当前参数下的 $f(n)$ 对 $P=1000000007$ 取模的最小非负余数。
- `1 alpha a0 ... ak` ：同时替换 $\alpha,a_0,\ldots,a_k$ ；$\beta$ 与 $k$ 不变。

替换后，全部项由新参数和上述递推重新定义。参数可能为负。

## 输入格式

第一行三个整数 $Q,\beta,k$ .第二行 $k+2$ 个整数 $\alpha,a_0,\ldots,a_k$ .接下来 $Q$ 行，每行给出一次操作，格式见形式化描述。

## 输出格式

每次查询输出一行一个整数；替换操作没有输出。

## 样例

### 样例 1

### 输入

```text
5 2 1
1 0 1
0 1
0 2
0 3
0 4
0 5
```

### 输出

```text
3
8
19
42
89
```

### 样例 2

### 输入

```text
5 1 0
-2 3
0 0
0 2
1 5 -1
0 0
0 3
```

### 输出

```text
1000000005
4
5
2
```

### 样例 3

### 输入

```text
3 0 1
7 3 -2
0 0
0 1
0 3
```

### 输出

```text
7
1
1000000004
```

## 样例解释

样例一满足 $f(n)=2f(n-1)+n$ .样例二在替换前满足 $f(n)=-2+3n$ ，替换后满足 $f(n)=5-n$ .样例三中 $\beta=0$ ，所以正下标项直接等于 $3-2n$ ，但零下标项仍为 $7$ .

## 数据范围与保证

对 **100% 数据**：

$1\le Q\le500$ ；$0\le k\le200$ ；$0\le n\le10^9$ ；$|\alpha|,|\beta|,|a_i|\le10^9$ ；操作编号为 $0$ 或 $1$ .

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