Grox的序列六¶
- 参考时间限制：0.5 秒。
- 实际时限：标准程序在目标环境的最慢用例中位耗时乘以 2，再按 0.5 秒向上取整。
- 内存限制：128 MB。
- 参考评测环境与测量
背景故事¶
是先知或神秘主义者为我们带来了电力、抗生素、现代卫生设备、航太科学以及数位计时器吗？绝对不是。是那些循序渐进，利用他人成就创造新奇迹的家伙。
——科学之书5（《Spore》，英文资料）
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¶
输入¶
5 2 1
1 0 1
0 1
0 2
0 3
0 4
0 5
输出¶
3
8
19
42
89
样例 2¶
输入¶
5 1 0
-2 3
0 0
0 2
1 5 -1
0 0
0 3
输出¶
1000000005
4
5
2
样例 3¶
输入¶
3 0 1
7 3 -2
0 0
0 1
0 3
输出¶
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% | 无额外条件 |