CF718C.Sasha and Array

斐波那契数列 $f_n$ 由以下递推式定义：

• $f_1=f_2=1$
• $f_n=f_{n-1}+f_{n-2}\;(n>2)$

你得到了 $n$ 个整数 $a_1,a_2,\cdots,a_n$.

你需要执行 $m$ 个操作，操作分两种：

• 1 l r x：对所有 $l\le i\le r$，将 $a_i$ 加上 $x$.
• 2 l r：求 $\sum\limits_{i=l}^r f_{a_i} \bmod (10^9+7)$.

第一行两个整数 $n,m$.

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$.

接下来 $m$ 行，每行三或四个整数表示一个操作.

对每个 $2$ 操作，一行一个整数表示答案.

$1\le n,m\le 10^5$

$1\le a_i\le 10^9$