Let's call the following 3x3 integer matrix transformation an MMD-transformation in 0-based indexation:
A_new [i][j] = sum ( A[x][y] * f(i, j, x, y) ) through all pairs x, y from 0 to 2 where f(i, j, x, y) ) = |i - x| + |j - y| + |i + j - x - y|
You are given a 3x3 matrix A₀. Let's denote by A_n matrix A₀ after N MMD-transformations with elements modulo 10⁹ + 7 . Your task is to find and output A_n.

Input
The first line contains T - the number of test cases. Then T test cases follow.
Each test case starts with line containing one integer N. Then 3 lines containing 3 integers each - matrix A₀.

Output
For each test case output matrix A_n in 3 lines containing 3 integers each. Don't forget that elements should be found modulo 10⁹ + 7.

Constraints

• T ≤ 30 000
• Initial elements of matrix A are from 0 to 99
• 1 ≤ N ≤ 10¹²
• 1 ≤ N ≤ 20 in 30% of the test data.