Big board - MarisaOJ: Marisa Online Judge

Big board

Time limit: 1000 ms
Memory limit: 256 MB
Given a board having $n$ rows and $m$ columns. Rows are numbered from $1$ to $n$, columns are numbered from $1$ to $m$. The value on the cell locating at row $i$ and column $j$ is $k^{(i-1)\times m + j - 1}$. Your task is to process a query $(a, b, c, d)$, calculate the sum of the rectangle with upper-left corner at $(a, b)$ and lower-right corner at $(c, d)$. ### Input - A single line contains seven integers $n,m,k,a,b,c,d$. ### Output - Print an integer is the answer modulo $111539768$. ### Constraints - $1 \le n,m \le 10^9$. - $2 \le k \le 10$. - $1 \le a \le c \le n$. - $1 \le b \le d \le m$. ### Example Input: ``` 4 4 2 1 2 2 3 ``` Output: ``` 102 ```