[Codeforces 718C] Sasha and Array

Problem Description

Sasha has an array of integers a1, a2, ..., an. You have to perform m queries. There might be queries of two types:

  1. 1 l r x — increase all integers on the segment from l to r by values x;
  2. 2 l r — find , where f(x) is the x-th Fibonacci number. As this number may be large, you only have to find it modulo 109 + 7.

In this problem we define Fibonacci numbers as follows: f(1) = 1, f(2) = 1, f(x) = f(x - 1) + f(x - 2) for all x > 2.

Sasha is a very talented boy and he managed to perform all queries in five seconds. Will you be able to write the program that performs as well as Sasha?


构造一个矩阵A=\begin{bmatrix}1 & 1\\ 1 & 0\end{bmatrix},那么斐波那契数列的第n项就是A^{n-1}





总的时间复杂度为O(m(\log n+\log a_{i}))