The Avengers finally gathered all the infinity stones together from different universe, and saved all lives that disappeared five years ago. However, Thanos comes again, from different universe. And this time, he'll eliminate the whole universe and create a new one, a grateful universe.

Thanos needs to compute how many energy he needs to consume to destruct and create a new universe. That is, he has to perform lots of matrix operations, including addition and multiplication. Now he threaten you to calculate these troublesome math, so that he can spend more time to deal with those ants ── those so called "Avengers".

Thanos thinking about this problem

If you click on this picture, something might happen...

You're given $R$ and $C$, indicate the row number and column number of matrix $M$.

An operation $OP$: + or *, and times $T$ will be given.

• For operation +, you need to calculate $\sum^T_{i=1}M$ and print the result.

  Note that:

  $$\sum^T_{i=1}M = \underbrace{M+M+\cdots+M}_T$$

• For operation *, you need to calculate $\prod^T_{i=1}M$ and print the result.

  Note that:

  $$\prod^T_{i=1}M = \underbrace{M\times M\times\cdots\times M}_T$$

This problem is partial judge. Note that in this problem, you can and you must use C++ to solve this problem.

in function.h, we have implemented the interfaces and some implementations of the class Matrix for you. What you need to do is to implement the remaining functions.

Functions we have implemented:

• Matrix()(constructor):

  Construct an empty Matrix object.

• const int &getrow():

  Get the row number of the corresponding matrix.

• const int &getcol():

  Get the column number of the corresponding matrix.

• const int *operator[] (const int &x) const:

  Implement operator[] for Matrix class. Make private member mat can be viewed using [] only. For example, we can view M.mat[x][y] by accessing M[x][y] for a Matrix object M.

• void print():

  The function to print the whole matrix.

Functions you have to implement:

• Matrix(int r, int c)(constructor):

  Construct an Matrix with row = r and column = c, and all elements equals to 0.

• int *operator[] (const int &x):

  Implement operator[] for Matrix class. Make private member mat can be accessed using [] only. For example, we can access M.mat[x][y] by accessing M[x][y] for a Matrix object M.

• Matrix operator+ (const Matrix &x) const:

  Perform "addition" operation, then return the result.

• friend Matrix operator* (const Matrix &x, const Matrix &y):

  Perform "multiplication" operation, then return the result. Note that this function is declared with friend.

In case of the result might be too large, all numbers should be module by 10007.

UPDATE: All nubmers should be module by 10007, and should output the positive one.(-2395%10007=7612)

The first line contains $R$, $C$, $T$, and $OP$, respectively.

There are $R$ lines below. Each line contains $C$ numbers. These $R\times C$ numbers indicate every element in matrix $M$.

$1\le R,\,C\le 100$, $0\le T\le 10^{18}$, $-10^5\le M\le 10^5$, where $M$ here incidates all elements in matrix $M$.

Output the result of the corresponding operation.

For output format, please refer to print function in function.h and the sample output.