C. Саша и массив
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Саши есть массив целых чисел a1, a2, ..., an. Необходимо быстро выполнить m запросов. Запросы бывают двух типов:

  1. 1 l r x — увеличить все числа на отрезке от l до r на значение x;
  2. 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.