Hello Codeforces, I need your help.

Given rectangular table A with n rows and m columns. This table has n × m cells, numbered sequentially with positive integers from top to bottom, from left to right. A[i][j] is a cell of rectangular table A at the cross of i-th row and j-th column. For the given value of x the sympathetic table is a table A with values in the cells equal to x in power of number of the corresponding cell. More formally A[i][j] = x^{(i−1)∗m + j}.

Given q queries of rectangular borders x1, x2, y1, y2 and modulo p, the answer for such query is the sum of numbers in corresponding rectangle by modulo.

More formally, find:

For example, the sympathetic table A, 3 by 4 for a given x looks like:

Constraints:

1 ≤ n, m, x, p ≤ 10⁹

1 ≤ q ≤ 10⁴

1 ≤ x1, x2 ≤ n, 1 ≤ y1, y2 ≤ m.

I spent much time for that problem, but I couldn't solve, please help me. Thanks in advance :)