Audio Quality

Wanla hopes to evaluate the audio quality of audio files in the new smart audio playback device IPOOD. A discrete audio file is considered as a sequence of length $N$: $A_1, A_2, \dots, A_N$. The audio quality of any range $[L, R]$ can be evaluated by the following score:

$$\left\{ \sum_{L < i < R} F[A_{i-1} + 1] F[A_{i+1} - 1] \right\} \pmod{10^9 + 7}$$

Here, $F$ is a recursively defined sequence, satisfying $F[1] = 1$, $F[2] = 2$, and $F[k+2] = F[k+1] + aF[k] + b$ for any $k \ge 1$, where $a$ and $b$ are integer coefficients.

To provide a better user experience, Wanla also hopes to optimize the given audio files. In this device, modifications to the audio file are also supported. For a given range $[L, R]$, the user is allowed to simultaneously increase or decrease $A[L]$ to $A[R]$ by 1.

Input

The first line contains two integers, the total length of the audio file $N$ and the number of modifications and queries $Q$. The second line contains two integers, representing the coefficients $a$ and $b$. The next line contains $N$ integers $A_1, \dots, A_N$, satisfying $1 \le A[i] \le 2 \times 10^9$. After that, there are $Q$ lines, each being one of the following three types:

• plus L R: Increase each element in the range $[L, R]$ of the audio file by 1.
• minus L R: Decrease each element in the range $[L, R]$ of the audio file by 1.
• query L R: Query the audio quality score of the range $[L, R]$.

In all modifications and queries, it is guaranteed that $L \le R$, and $A[i]$ is strictly greater than the number of modifications performed (modifications include both plus and minus operations).

Output

Output several lines, each containing one integer for each query.

Constraints

For 15% of the data, $N \le 8000, Q \le 8000$. For 100% of the data, $N \le 300000, Q \le 10000, 0 \le a, b \le 10^9$. Additionally: There is 15% of the data where every modification range is $[1, N]$. There is 30% of the data where $a = 0, b = 1$.

Examples

Input 1

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

Output 1

64
1766
104
7479
7687

Input 2

7 12
123456789 987654321
1111111111 1222222222 1333333333
1444444444 1555555555 1666666666 1777777777
query 2 4
query 3 7
plus 3 5
minus 4 6
plus 5 7
query 2 4
query 1 6
plus 4 7
minus 1 4
query 3 7
query 2 6
query 1 7

Output 2

528103209
239947280
528103209
229970829
524160263
336413855
113033289