3529 -- Matrix Analysis

Online Judge

Problem Set

Authors

Online Contests

User

Language:

Matrix Analysis

Time Limit: 1000MS		Memory Limit: 131072K
Total Submissions: 168		Accepted: 39

Description

Given two integral m × n matrices A = {a_ij} and B = {b_ij}, we define a sequence of matrices S_B = {B^k} with B¹ = B where, for each k > 1,

$b_{ij}^k=\sum_{p=1}^{i-1}a_{pj}b_{pj}^k+\sum_{q=1}^{j-1}a_{iq}b_{iq}^k+b_{ij}^{k-1}$ .

Write a program that is capable of evaluating S_B efficiently.

Input

The input consists of a single test case and is given in the following format:

Bounds on the values are: 1 ≤ m, n ≤ 20; 1 ≤ t ≤ 1000; 0 ≤ a_ij, b_ij ≤ 10; 1 ≤ i_t ≤ m; 1 ≤ j_t ≤ n; 1 ≤ k_t ≤ 10⁹.

Output

For each t, output b_{i_tj_t}^k_t mod 1,000,000,007.

Sample Input

Sample Output

Hint

1,000,000,007 is a prime.

Source