Arya is in a problem in the city, Braavos. She has to solve a problem given by the faceless man in order to get free from the city.

She has a matrix A of size 2x2. Initially, the elements of the matrix are:

a11	a12
a21	a22

In each iteration, she has to change the elements of the matrix A as follows:

a_11(new) = a₁₁ + (a₁₁ + a₂₂)

a_12(new) = a₁₂ + (a₁₂ + a₂₁)

a_21(new) = a₂₁ + (a₂₁ + a₁₂)

a_22(new) = a₂₂ + (a₂₂ + a₁₁)

She is neither good at programming nor at mathematics, so she needs your help.

You have given the number of iteration n. You have to tell the elements of A after n^th iteration.

Since the numbers are very large, take modulo 10^9 + 7.

Input Format :

First line will contain t, number of testcases. Then the testcases follow.

Each testcase will contains an integer, n.

The next line will contain four space separated integers a₁₁ a₁₂ a₂₂ a_21.

Output Format :

For each test case, print space separated four values in the new line: a₁₁ a₁₂ a₂₂ a₂₁

Constraints :

• 1 <= t <= 100000
• 1 <= n <= 10^18
• 1 <= a_11, a_12, a_22, a₂₁ <= 10^9

Subtasks:

#1 (20 pts): 1 <= t, n, a_11, a_12, a_22, a₂₁ <= 1000

#2 (80 pts): Original Constraints