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
```
