题目描述

在本题中，我们用 $f_i$ 来表示第 $i$ 个斐波那契数（$f_1 = f_2 = 1$，$f_i = f_{i - 1} + f_{i - 2}$（$i \geq 3$））。

给定一个长度为 $n$ 的序列 $a$。有 $m$ 次操作，操作有两种：

1. 将 $a_l \sim a_r$ 加上 $x$。
2. 求 $（\sum_{i = l}^{r} f_{a_i} ） \mod (10^9 + 7)$。

输入描述

第一行两个正整数 $n$ 和 $m$（$1 \leq n, m \leq 10^5$）。

第二行 $n$ 个正整数 $a_i$（$1 \leq a_i \leq 10^9$）。

接下来 $m$ 行，每行包含下面两种形式中的一种，含义如题面所述：

• 1 l r x，$1 \leq l \leq r \leq n$，$1 \leq x \leq 10^9$；
• 2 l r，$1 \leq l \leq r \leq n$。

输出描述

对于每个查询，输出答案。

示例

输入

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

输出

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$。
• 在第二次操作后，数组 $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$。