Copy the array#8256
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** – Replace the value at position with . - **SUM** – Compute the sum of all elements in [left; right] and return the result modulo 10^9+7.
The first line contains a single integer (1 \leq A \leq 10^9), which is the initial element of the array.
The second line contains the integer (1 \leq Q \leq 2 \cdot 10^5), representing the number of queries.
The next 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** – This query changes the element at position to (1 \leq pos \leq 10^{18}, 1 \leq val \leq 10^9). - **SUM** – This query calculates the sum of elements in [left; right] (1 \leq left \leq right \leq 10^{18}).
It is guaranteed that the values of , , and in the **CHANGE** and **SUM** queries will not exceed the current size of the array.
For each **SUM** query, output a single number: the sum of the specified segment of the array, taken modulo 10^9+7.
Example 1