11641164 SUSTech Online Judge
Problem 1164 -- Failed in Linear Algebra

1164: Failed in Linear Algebra

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


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.


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


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

2 2
1 2
2 1
2 2
3 3

Sample Output

11 10
13 14


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); }