Description

Boss Wan wants to implement an evaluation of the audio quality performance of wave files in the new smart music player $\operatorname{IPOOD}$. A discrete wave file is considered as an integer sequence of length $N$: $A_1, A_2, \cdots, A_N$. The audio quality evaluation can be computed for any interval $[L, R]$, and the score depends on the following expression:

$$\sum_{L<i<R}F[A_{i-1}+1]F[A_{i+1}-1] \operatorname{mod}\;(10^9+7)$$

Here $F$ is an inductively defined sequence, satisfying $F_1=1$, $F_2=2$, and $F_{k+2}=F_{k+1}+aF_{k}+b$ for any $k>0$.

Here $a$ and $b$ are non-negative integer coefficients. To provide a better user experience and to allow optimization of the given wave file, the device should also support modifications to the wave file. For a given interval $[L, R]$, the user is allowed to increase $A_L$ through $A_R$ by one simultaneously, or decrease them by one simultaneously.

Input Format

The first line contains two positive integers: the total length $N$ of the wave file, and the total number $Q$ of modifications and queries.

The second line contains two integers, the coefficients $a$ and $b$.

Then, over several lines, $N$ positive integers $A_1$ through $A_N$ are given, satisfying $1 \leq A_i \leq 2 \times 10^9$.

Then follow $Q$ lines, each in one of the following three forms:

• $\text{plus}\;L\;R:$ increase every element with index in $[L, R]$ by one.
• $\text{minus}\;L\;R:$ decrease every element with index in $[L, R]$ by one.
• $\text{query}\;L\;R:$ ask for the audio quality score of the interval $[L, R]$. In both modifications and queries, it is guaranteed that $L \leq R$, and that $A_i$ is strictly greater than the total number of modifications plus one (modification operations include both $\text{plus}$ and $\text{minus}$).

Output Format

Output several lines, each corresponding to one query. For each query, output one integer.

7 7
1 0
3 4 5 6 7 8 9
query 2 4
query 3 7
plus 3 5
query 2 4
plus 4 7
query 3 7
query 1 7

64 
1766 
104 
7479 
7687

Hint

$N\leq 3\times10^5,Q\leq10^4,0\leq a,b\leq10^9$.

Translated by ChatGPT 5