У Саши есть массив целых чисел a1, a2, ..., an. Необходимо быстро выполнить m запросов. Запросы бывают двух типов:
- 1 l r x — увеличить все числа на отрезке от l до r на значение x;
- 2 l r — найти
, где f(x) — х-е число Фибоначчи. Поскольку эта величина может быть очень большой, выведите остаток от её деления на 109 + 7.
В данной задаче определим числа Фибоначчи следующим образом: f(1) = 1, f(2) = 1, f(x) = f(x - 1) + f(x - 2) для x > 2.
Саша — очень талантливый мальчик. Он в уме отвечает на все запросы за пять секунд. Получится ли у вас написать программу, которая не уступит ему в скорости?
Выходные данные
Для каждого запроса второго типа в отдельной строке выведите ответ на запрос по модулю 109 + 7.
Примечание
Изначально массив a равен 1, 1, 2, 1, 1.
Ответ на первый запрос равен f(1) + f(1) + f(2) + f(1) + f(1) = 1 + 1 + 1 + 1 + 1 = 5.
После запроса 1 2 4 2 массив 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.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
1 1 2 1 1
2 1 5
1 2 4 2
2 2 4
2 1 5
|
5
7
9
|