Powers of a matrix P61833


Statement
 

pdf   zip

html

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