We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Fundamentals
  4. Mutual Recurrences

Mutual Recurrences

Since you know how to compute large Fibonacci numbers quickly using matrix exponentiation, let's take things to the next level.

Let , , , , , , and be positive integers. We define two bi-infinite sequences

and
as follows:

and

Given and the eight integers above, find and . Since these values can be very large, output them modulo .

This link may help you get started: http://fusharblog.com/solving-linear-recurrence-for-programming-contest/

Input Format

The first line of input contains , the number of test cases.
Each test case consists of a single line containing nine space separated integers: , , , , , , , and , respectively.

Constraints


Output Format

For each test case, output a single line containing two space separated integers, and .

Sample Input

3
1 2 3 1 1 2 3 1 10
1 2 3 2 2 1 1 4 10
1 2 3 4 5 6 7 8 90

Sample Output

1910 1910
909323 11461521
108676813 414467031

Explanation

In the second test case, the following is a table of values and for :

Remember that if .

One can verify this table by using the definition above. For example: