Олимпиадный тренинг

Задача . E. Опять запросы к массиву...


Задача

Темы: Структуры данных математика *2500

Дан массив, состоящий из 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).


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

time 5000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++5
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет