eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Скопіюйте масив

Скопіюйте масив

Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB

У вас є масив. Спочатку вiн зовсiм малесенький – cкладається всього з одного числа.

Та з кожним запитом вiн ставатиме все бiльшим i бiльшим. Чи впораєтеся ви з цим масивом i запитами на ньому?Формальніше, вам необхідно обробити такі запити:

  • COPY – скопіювати масив та додати його в кінець

  • CHANGE pos val – замінити значення в позиції pos на val

  • SUM left right – обчислити суму всіх елементів на відрізку [left;right] за модулем 10^9+7

Вхідні дані

У першому рядку вхідних даних міститься єдине число A (1 ≤ A ≤ 10^9) - єдиний елемент масиву

У другому рядку задано число Q(1 ≤ Q ≤ 2*10^5) – кількість запитів.

В наступних Q запитів в наступному форматі :

  • COPY – запит першого типу

  • CHANGE pos val – запит другого типу (1 ≤ pos ≤ 10^18 ,1 ≤ val ≤ 10^9)

  • SUM left right – запит третього типу (1 ≤ left ≤ right ≤ 10^18)Гарантується, що pos, left, right із другого і третього запитів не перевищують поточний розмір масиву.

Вихідні дані

Для кожного запиту третього типу виведіть єдине число – суму всіх чисел на відповідному відрізку за модулем 10^9+7.

Приклад

Вхідні дані #1
1
7
COPY
SUM 1 2
CHANGE 2 4
COPY
SUM 2 3
CHANGE 3 10
SUM 1 4
Вихідні дані #1
2
5
19