Waveform Audio Quality Evaluation and Modification

In this problem, you are given a waveform file represented as an integer sequence A[1], A[2], ..., A[N]. The new smart audio device IPOOD evaluates the audio quality performance over any sub-interval of the waveform file. You are required to support two types of operations:

• Evaluation Query: For a given interval [L, R] (1-indexed), the audio quality performance is defined as:

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

The function F is defined by the recurrence:

$$F(1)=1,\quad F(2)=2,\quad F(k+2)=F(k+1)+a \cdot F(k)+b \quad\text{for } k>0$$

• Update Query: For a given interval [L, R], you may either increase or decrease each element in the interval by 1.

You are given Q queries. Each query is one of the following two types:

1. Evaluation Query: Input format "1 L R". For each such query, calculate and output the performance as defined above.
2. Update Query: Input format "2 L R d", where d is either 1 (to increase by one) or -1 (to decrease by one). Update each element A[L] to A[R] accordingly.

Note that the indices in the performance evaluation are taken based on the current state of the array A (which is 1-indexed), and in computing the performance for an interval [L,R], you should sum for all indices i such that L < i < R the product:

$$F(A_{i-1}+1) \cdot F(A_{i+1}-1)$$

All computations are done modulo 10^9+7.

inputFormat

The first line contains four integers: N Q a b where N is the length of the waveform, Q is the number of queries, and a and b are positive integers used in the recurrence for F.

The second line contains N integers: A[1] A[2] ... A[N], representing the waveform file.

Each of the following Q lines represents a query in one of the following formats:

• 1 L R — Evaluation Query. Compute the audio quality performance for the subarray A[L] ... A[R].
• 2 L R d — Update Query. Increase (if d = 1) or decrease (if d = -1) each element in the interval A[L] ... A[R] by 1.

It is guaranteed that the operations will not cause any argument of the function F to be less than 1.

outputFormat

For each evaluation query (query type 1), output a single line containing the calculated performance (modulo 10^9+7).

sample

5 5 1 1
1 2 3 4 5
1 1 5
2 2 4 1
1 2 5
2 1 3 -1
1 1 3

69
133
2

</p>