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。