| Codeforces Round 373 (Div. 1) |
|---|
| Закончено |
У Саши есть массив целых чисел 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.
Саша — очень талантливый мальчик. Он в уме отвечает на все запросы за пять секунд. Получится ли у вас написать программу, которая не уступит ему в скорости?
В первой строке входных данных содержатся два числа n и m (1 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000) — количество элементов массива и количество запросов соответственно.
В следующей строке содержатся n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109).
Следующие m строк описывают запросы. В каждой из них находятся числа tpi, li, ri и, возможно, xi (1 ≤ tpi ≤ 2, 1 ≤ li ≤ ri ≤ n, 1 ≤ xi ≤ 109), (tpi = 1 соответствует запросу первого типа, tpi = 2 — второго).
Гарантируется, что во входных данных будет присутствовать хотя бы один запрос второго типа.
Для каждого запроса второго типа в отдельной строке выведите ответ на запрос по модулю 109 + 7.
5 4
1 1 2 1 1
2 1 5
1 2 4 2
2 2 4
2 1 5
5
7
9
Изначально массив 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.
