Because of necessary software maintenance, Jutge.org may not work well on the afternoons of the 20th and 21th of april.

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} modm.

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} modm 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++ Python
- User solutions
- C++ Python