U268603 Fibonacci

$\text{zxh}$ 非常讨厌统计数据，于是有了这道题。

$f_i$ 表示斐波那契数列第 $i$ 项。 一个长度为 $n$ 序列 $A\{a_1,a_2,...,a_n\}$，$m$ 个操作。 操作一：$3$ 个参数 $l,r,k$，对于所有 $a_i(l\le i\le r)$，$a_i\gets a_i+k$。 操作二：$3$ 个参数 $l,r,k$，对于所有 $a_i(l\le i\le r),a_i\gets k$。 操作三：$2$ 个参数 $l,r$，询问 $(\sum_{i=l}^r{f_{a_i}}) \bmod 10^9+7$ 的值。

一个整数 $n$，接下来 $n$ 个整数表示 $A$。 一个整数 $m$，接下来 $m$ 行，每行代表一个操作。 一行一个整数 $opt$，如果 $opt=1$，表示操作一，接下来三个整数 $l,r,k$，如果 $opt=2$，代表操作二，接下来三个整数 $l,r,k$，如果 $opt=3$，代表操作三，接下来两个整数 $l,r$。

对于每个操作三，输出一行表示答案。

对于 $30\%$ 的数据，$1\le n,m\le 1000,-10^9\le k\le 10^9,1\le a_i\le10^9$。 对于 $100\%$ 的数据，$1\le n,m\le5\times10^5,1\le l \le r\le n,-10^9\le k\le 10^9,1\le a_i\le10^9$，保证任意时刻满足 $a_i\ge1$。 建议开启 $\text{O2}$ 优化。