Powers of a matrix P61833

Given a $2 \times 2$ matrix $M$ of natural numbers, a natural number $n$ and a natural number $m$, compute $M^n$. To avoid overflows, compute every element of $M^n \bmod m$.

Input

Input consists of several cases, each with $M_{11}$, $M_{12}$, $M_{21}$ and $M_{22}$ in this order, followed by $n$ and $m$. Assume that the elements of $M$ are not larger than $500$, $0 \le n \le 10^9$, and $2 \le m \le 1000$.

Output

For every case, print the elements of $M^n \bmod m$ in two lines following the format of the sample. Print a line with 10 dashes after every matrix.