Matrix must die
50% Success398 Attempts50 Points2s Time Limit256MB Memory1024 KB Max Code

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 109 + 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 109 + 7.

Constraints

  • T ≤ 30 000
  • Initial elements of matrix A are from 0 to 99
  • 1 ≤ N ≤ 1012
  • 1 ≤ N ≤ 20 in 30% of the test data.
Examples
Input
2
1
1 1 1
1 1 1
1 1 1
1
1 2 3
4 5 6
7 8 9
Output
36 26 26 
26 20 26 
26 26 36 
228 164 142 
152 100 108 
118 96 132

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading Editor...
Results