Скопируйте массив
У вас есть массив, который изначально состоит всего из одного элемента.
С каждым запросом массив будет увеличиваться. Сможете ли вы справиться с этим массивом и обрабатывать запросы?
Вам нужно обработать следующие типы запросов:
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.