SP4458 RAINBOW2 - Rainbow

This time Blue Mary continues doing meaningless calculations! (see problem [SPY](http://www.spoj.com/problems/SPY2)) She is interested in calculating the **K**-th power of a very large **N**x**N** matrix A, where A $ _{i,j} $ = i \* **D** + **Q** $ ^{j} $ i and j are 0-based index of the row and column of element A $ _{i,j} $ , respectively. Now she needs your help (again). To keep the output small, you are only asked to output some of its elements.

Multiple test cases. The first line of each test case contains 5 space-separated integers **N**, **K**, **D**, **Q**, **M** in this order. **M** lines follow, each contains two space-separated integers **R $ _{i} $** and **C $ _{i} $** . Input terminates by EOF. All input numbers are non-negative integers and no more than 10 $ ^{9} $ .(**D**, **R $ _{i} $** and **C $ _{i} $** may be 0, others must be positive integers.) **N** and **M** will be no more than 10 $ ^{5} $ . **R $ _{i} $** and **C $ _{i} $** will be less than **N**. Input is almost uniformly-random generated, and the number of "large" test cases is relatively small.

For each test case output exactly **M** lines. Each line contains only one integer: The number at the **R $ _{i} $** -th row and **C $ _{i} $** -th column (0-based) of the matrix **A $ ^{K} $** . As the result may be quite large, output it modulo 10 $ ^{9} $ +2015.