Matrix Exponentiation

Given a 2x2 matrix ( A = \begin{pmatrix} a & b \ c & d \end{pmatrix}) and a non-negative integer ( n ), compute ( A^n ) modulo ( 10^9+7 ). This problem requires you to use fast exponentiation techniques (also known as binary exponentiation) to efficiently compute the power even when ( n ) is large.

You are expected to read the input from standard input (stdin) and output the result to standard output (stdout). The result consists of the matrix entries of ( A^n ) in row-major order, each separated by a space.

inputFormat

The input consists of five integers: ( a ), ( b ), ( c ), ( d ) and ( n ) separated by spaces. They represent the matrix ( A = \begin{pmatrix} a & b \ c & d \end{pmatrix}) and the exponent ( n ).

outputFormat

The output should be four integers separated by spaces. These numbers correspond to the matrix ( A^n ) in row-major order: first row then second row. All computations are done modulo ( 10^9+7 ).## sample

2 3 4 5 2

16 21 28 37