Problem F: Failed in Linear Algebra

Problem F: Failed in Linear Algebra

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 587  Solved: 86
[Submit][Status][Web Board]

Description

One day, Wavator is taking his Linear algebra course. He hates calculating the expression of matrix so he wants to develop a calculator to help him. But, he got 59 in last years’ DSAA course, so he turns you for help.
n  square matrices of size m are given, and we defines an operation like “(1+2)*1” which means the matrix 1 plus matrix 2 and then multiplies matrix 1.
Wavator only wants to calculate “+” and “-” and “*”, so he denotes that “+”  means A + B = C where C[i][j] = A[i][j] + B[i][j] .The rule of “-” is similar with "+".
Notice that in matrix multiplication, a*b and b*a is not the same.
Since the number may be too large during the calculation process, in each step you should mod 1000000007.

Input

The first line contains an integer T, meaning there will be T (T<=10) test cases.
For each test cases, the first line is n and m (n <= 10 and m <= 50), then there will be n parts, each part is a m * m matrix a, 0<=a[i][j] <= 10000, matrixes are numbered from 1 to n, then there will be a string s, the length of s is not greater than 50, and it is valid. (contains only 1~n numbers (index of matrixes) and “+”, “-”, “*” only) .

Output

For each test case, print m lines, each line should contain m integers, meaning the value of the final matrix at this line and this column. 

Sample Input

1
2 2
1 2
2 1
2 2
3 3
(1+2)*1

Sample Output

11 10
13 14

HINT


Codes of mod in c++ lang. similar using java.



const int MOD = 1000000007;



inline int add(int x, int y) { return (x + y) % MOD; } 



inline int sub(int x, int y) { return (x - y + MOD) % MOD; }



inline int mul(int x, int y) { return static_cast<int>((long long) x * y % MOD); }





[Submit][Status]