Скопіюйте масив
У вас є масив. Спочатку в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.