Matrix Submatrix K-ary XOR Sum

Given an n \times m matrix where the element at row i and column j is \( (i-1)m+j \). For a submatrix with top-left coordinate \((x,y)\) and bottom-right coordinate \((z,w)\), compute the k-ary xor sum of all elements in the submatrix.

The k-ary xor sum is defined as the digit-wise addition modulo \(k\) (i.e. without carrying). In particular, if a number \(a\) is represented in base \(k\) as \((a_d a_{d-1} \dots a_0)_k\) and a number \(b\) as \((b_d b_{d-1} \dots b_0)_k\) (padding with leading zeros if necessary), their xor sum is given by \[ c = (a \oplus b) = \sum_{i \ge 0} ((a_i + b_i) \bmod k) \cdot k^i. \] For example, in base 9, \((45)_9 \oplus (87)_9 = (33)_9\) because \(4+8 \equiv 3 \pmod{9}\) and \(5+7 \equiv 3 \pmod{9}\).

inputFormat

The input consists of a single line containing seven integers: \(n\), \(m\), \(x\), \(y\), \(z\), \(w\), and \(k\), where \(1 \le x \le z \le n\) and \(1 \le y \le w \le m\).

outputFormat

Output a single integer representing the k-ary xor sum of the elements in the specified submatrix.

sample

3 4 1 2 3 4 10

36