Given a 2 × 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} mod*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 ≤ *n* ≤ 10^{9},
and 2 ≤ *m* ≤ 1000.

**Output**

For every case,
print the elements of *M*^{n} mod*m* in two lines
following the format of the sample.
Print a line with 10 dashes after every matrix.

Public test cases

**Input**

2 7 1 4 2 100 2 7 1 4 2 5 15 2 3 4 0 1000 500 499 499 498 123456789 1000

**Output**

11 42 6 23 ---------- 1 2 1 3 ---------- 1 0 0 1 ---------- 792 815 815 422 ----------

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++