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

Let $\boldsymbol{\alpha}$, $\boldsymbol{b}$, $\textbf{C}$, $\boldsymbol{d}$, $\boldsymbol{\mathrm{~e~}}$, $\mbox{f}$, $\mathrm{~g~}$ and $\mbox{h}$ be positive integers. We define two bi-infinite sequences
$(\ldots,x_{-2},x_{-1},x_{0},x_{1},x_{2},\ldots)$
and
$(\ldots,y_{-2},y_{-1},y_{0},y_{1},y_{2},\ldots)$
as follows:

$x_n=\begin{cases}x_{n-a}+y_{n-b}+y_{n-c}+n\cdot d^n&\text{if}\ n\geq0\\ 1&\text{if}\ n<0\end{cases}$

and

$y_n=\begin{cases}y_{n-e}+x_{n-f}+x_{n-g}+n\cdot h^n&\text{if}\ n\geq0\\ 1&\text{if}\ n<0\end{cases}$

Given $n$ and the eight integers above, find $x_n$ and $y_n$. Since these values can be very large, output them modulo $\mathbf{10^{9}}$.

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

Input Format

The first line of input contains $\mathbf{T}$, the number of test cases.

Each test case consists of a single line containing nine space separated integers: $\boldsymbol{\alpha}$, $\boldsymbol{b}$, $\textbf{C}$, $\boldsymbol{d}$, $\boldsymbol{\mathrm{~e~}}$, $\mbox{f}$, $\mathrm{~g~}$, $\mbox{h}$ and $n$, respectively.

Constraints

$1\leq T\leq100$

$1\leq a,b,c,d,e,f,g,h<10$

$1\leq n\leq10^{18}$

Output Format

For each test case, output a single line containing two space separated integers, $x_n\:\text{mod}\:10^9$ and $y_n\:\text{mod}\:10^9$.

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 $x_i$ and $y_i$ for $0\leq i\leq10$:

$\begin{array}{c|ccc}i&x_i&y_i&y_i\\ \hline0&3&11\\ 1&7&11\\ 2&19&41\\ 3&187&141\\ 4&1831&197\\ 5&631&5793\\ 6&2443&27097\\ 7&10249&125297\\ 8&40245&571811\\ 9&201975&2574881\\ 10&919373&14674881\\ \end{array}$

Remember that $x_i=y_i=1$ if $i<0$.

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

$\begin{aligned}x_5&=x_{5-1}+y_{5-2}+y_{5-3}+y_{-3}+5\cdot2^5\\ &=x_{4}+y_{3}+y_{2}+160\\ &=81+241+49+160\\ y_6&=y_{5-2}+x_{5-1}+x_{5-1}+5\cdot4^5\\ &=y_{5-2}+x_{5-1}+x_{4}+x_{5-1}+5\cdot4^5\\ &=21+x_{4}+x_{4}+x_{5}+5120\\ &=5721+161+181+5120\\ &=x_{2-1}+y_{4-2}+y_{2-3}+2\cdot2^2\\ &=x_{1-1}+y_{0}+y_{4-1}+y_{2}+2\cdot2^2\\ &=7+3+1+8\\ \end{aligned}$

见题面

见题面