E. Опять запросы к массиву...
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив, состоящий из n целых чисел: a1, a2, ..., an. Вам необходимо быстро выполнять запросы двух типов:

  1. Присвоить всем элементам от l до r включительно значение x. После такого запроса значения элементов массива al, al + 1, ..., ar становятся равны x.
  2. Посчитать и вывести сумму , где k не превосходит 5. Так как значение суммы может оказаться достаточно большим, нужно выводить остаток от его деления на 1000000007 (109 + 7).
Входные данные

В первой строке записано два целых числа n и m (1 ≤ n, m ≤ 105) — количество чисел в массиве и количество запросов соответственно. Во второй строке записано n целых чисел: a1, a2, ..., an (0 ≤ ai ≤ 109) — начальные значения элементов массива.

Далее следует m запросов, по одному в каждой строке:

  1. Запрос на присвоение имеет следующий формат: «», (1 ≤ l ≤ r ≤ n; 0 ≤ x ≤ 109).
  2. Запрос на подсчет суммы имеет следующий формат: «», (1 ≤ l ≤ r ≤ n; 0 ≤ k ≤ 5).

Все числа во входных данных целые.

Выходные данные

В ответ на каждый запрос на подсчет суммы выведите одно целое число — требуемую сумму по модулю 1000000007 (109 + 7).

Примеры
Входные данные
4 5
5 10 2 1
? 1 2 1
= 2 2 0
? 2 4 3
= 1 4 1
? 1 4 5
Выходные данные
25
43
1300
Входные данные
3 1
1000000000 1000000000 1000000000
? 1 3 0
Выходные данные
999999986