Powers of a matrix P61833


Statement
 

pdf   zip

thehtml

Given a 2 × 2 matrix M of natural numbers, a natural number n and a natural number m, compute Mn. To avoid overflows, compute every element of Mn modm.

Input

Input consists of several cases, each with M11, M12, M21 and M22 in this order, followed by n and m. Assume that the elements of M are not larger than 500, 0 ≤ n ≤ 109, and 2 ≤ m ≤ 1000.

Output

For every case, print the elements of Mn 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