# [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?

## Solution

mdzz矩阵快速幂必须在外面弄好，不然进去就要带个$log$然后就GG