Power Generation Device

Kim Hanyang, who found a job right after graduating from university, is developing a new power generation device at an LG Electronics research lab. The device is a pyramid of 1 by 1 modules, as shown in the \[Figure] below. The device is N floors tall, from floor 1 closest to the ground to floor N farthest from it. Floor 1 has N modules, floor 2 has N - 1 modules, and so on, up to floor N, which has 1 module in a row. The module in the C-th position on floor R is written (R, C). The leftmost and rightmost modules on each floor are production modules that make electricity from sunlight. Floor N has only one production module, in the middle. A production module's charging speed depends on its height above the sun, so it generates more electricity on higher floors, regardless of its horizontal position. Let A be the charging speed of the production module on floor 1, and let B be the increase in charging speed for each floor up. The charging speed of a production module by floor then forms an arithmetic sequence with first term A and common difference B, where B is a positive integer. All other modules are merge modules. A merge module takes the sum of the two modules directly above it on the upper floor. That is, the charging speed of the merge module at (R, C) equals the sum of the charging speeds of the modules at (R + 1, C - 1) and (R + 1, C). Kim Hanyang needs a program that computes the charging speed of each module to check whether the device works correctly. Use the information above to write this program.

The first line contains three positive integers A, B, and N, separated by spaces. (1 ≤ A, B ≤ 10^9; 1 ≤ N ≤ 2 × 10^6) The second line contains the number of test cases T. (1 ≤ T ≤ 2 × 10^5) The next T lines each contain two positive integers R and C, separated by a space. (1 ≤ R, C ≤ N; R + C ≤ N + 1)

For each test case, print the charging speed of the module at (R, C) modulo 10^9 + 7.