matrix-must-die

Let's call the following   3x3 integer matrix transformation an MMD-transformation in 0-based indexation:
Anew [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 A0.  Let's denote by An matrix A0 after N MMD-transformations with elements modulo 10^9 + 7 . Your task is to find and output An.

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 A0.

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

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

SAMPLE INPUT
2
1
1 1 1
1 1 1
1 1 1
1
1 2 3
4 5 6
7 8 9

SAMPLE OUTPUT
36 26 26 
26 20 26 
26 26 36 
228 164 142 
152 100 108 
118 96 132

Source: hackerearth | Difficulty: HARD
Tags: Matrices

Mathematics


Solutions: