Copy the array
You are given an array that initially contains just one number.
With each query, the array will grow larger. Can you manage this array and process the queries? Specifically, you need to handle the following types of queries:
COPY – Duplicate the array and append it to the end.
CHANGE pos val – Replace the value at position pos with val.
SUM left right – Compute the sum of all elements from left to right, inclusive, and return the result modulo
10^9+7.
Input
The first line contains a single integer A (1 ≤ A ≤ 10^9), which is the initial element of the array.
The second line contains the integer Q (1 ≤ Q ≤ 2*10^5), representing the number of queries.
The next Q lines contain one query each in one of the following formats:
COPY – This query duplicates the current array and appends it to the end.
CHANGE pos val – This query changes the element at position pos to val (1 ≤ pos ≤
10^18, 1 ≤ val ≤10^9).SUM left right – This query calculates the sum of elements from position left to right (1 ≤ left ≤ right ≤
10^18).
It is guaranteed that the values of pos, left, and right in the CHANGE and SUM queries will not exceed the current size of the array.
Output
For each SUM query, output a single number: the sum of the specified segment of the array, taken modulo 10^9+7.