← 返回题目列表

Codeforces · 718/C

C. 萨莎和阵列

中文机器翻译题面 查看原题

Sasha 有一个整数数组 a1, a2, ..., an。您必须执行 m 次查询。可能有两种类型的查询:

1. 1 l r x — 将 l 到 r 段上的所有整数增加 x 值;
2. 2 l r — 求 $$\sum_{i=l}^{r} f(a_i)$$,其中 f(x) 是第 x 个斐波那契数。由于这个数字可能很大,您只需对 109 + 7 求模即可。

在此问题中,我们将斐波那契数定义如下:对于所有 x > 2,f(1) = 1、f(2) = 1、f(x) = f(x - 1) + f(x - 2)。

Sasha 是一个非常有才华的男孩,他成功地在五秒钟内完成了所有查询。你能编写出与 Sasha 一样出色的程序吗?

输入

输入的第一行包含两个整数 n 和 m (1 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000)——分别是数组中的元素数量和查询数量。

下一行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109)。

然后接下来的 m 行是查询描述。它们中的每一个都包含整数tpi、li、ri并且可以是xi(1≤tpi≤2、1≤li≤ri≤n、1≤xi≤109)。这里tpi = 1对应于第一类型的查询,tpi对应于第二类型的查询。

保证输入至少包含一个第二类型的查询。

输出

对于第二种类型的每个查询,打印答案模 109 + 7。

示例

输入 #1

5 4
1 1 2 1 1
2 1 5
1 2 4 2
2 2 4
2 1 5

输出 #1

5
7
9

注意

最初,数组 a 等于 1, 1, 2, 1, 1。

第二种类型的第一个查询的答案是 f(1) + f(1) + f(2) + f(1) + f(1) = 1 + 1 + 1 + 1 + 1 = 5。

查询1 2 4 2数组a后等于1,3,4,3,1。

第二种类型的第二个查询的答案是 f(3) + f(4) + f(3) = 2 + 3 + 2 = 7。

第二种类型的第三个查询的答案是 f(1) + f(3) + f(4) + f(3) + f(1) = 1 + 2 + 3 + 2 + 1 = 9。