### PROBLEM LINKS

### DIFFICULTY

HARD

### EXPLANATION

First, we consider the case where **X, Y** > 0. Let **f**(**i**) be the vector (**S**[**i**] **S**[**i**+1] 1), then there is a 3*3 matrix A such that **f**(**i**+1) = **A f**(**i**). Now, our task is calculating the number of vectors **f**(**k**) = (**C m** 1) satisfying **L**[**i**] <= **k** <= **R**[**i**], and 0 <= **m** < **P**.

The sequence **f** has a period **r** (at most **P**^2), since **A** is a regular matrix. That is **f**(**k+r**) = **f**(**k**), for all **k** >= 1.

The first part of solving the problem is calculating a period **r** and integers **k** which satisfy **f**(**k**) = (**C m 1**) for each **m**. Finding minimum **k** such that **f**(**k**+1) = **f**(1) is enough to calculate a period **r**. Therefore, we should search **P+1** vectors in the sequence **f**, and it can be calculated by using baby-step-giant-step. At first, calculate the vectors **A^d f**(**1**) for 0 <= **d < L**, and store the vectors. For finding a vector **v**, we calculate (**A^L**)^**e v** for 0 <= **e < r/L**, and search these vectors in the set of all vectors **A^d f**(1). The precalculation takes **O**(**L**) time, and finding a vector in the sequence takes **O(r/L)** time if hashes are used for searching. Here, let’s set **L** = **P**^1.5, then this part takes **O**(**P**^1.5) + (**P+1**) * **O**(**P**^2 / **P**^1.5) = O(P^1.5) time.

The second part is calculating the answer for each intervals. It can be calculated by using binary search. It takes **O**(**Q** log **P**) time.

If **X** and/or Y are 0, above algorithm cannot be applied, because the matrix **A** may be singular. However, these cases are not so difficult. A similar method can be used for the case **X** > 0 or **Y** > 0, and the problem becomes trivial for the case **X** = **Y** = 0.

### SETTER’S SOLUTION

Can be found here.