Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Matrix Analysis
Time Limit: 1000MSMemory Limit: 131072K
Total Submissions: 150Accepted: 35

Description

Given two integral m × n matrices A = {aij} and B = {bij}, we define a sequence of matrices SB = {Bk} with B1 = 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 SB efficiently.

Input

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

mnt
a11a12a1n
a21a22a2n
am1am2amn
b11b12b1n
b21b22b2n
bm1bm2bmn
i1j1k1
i2j2k2
itjtkt

Bounds on the values are: 1 ≤ m, n ≤ 20; 1 ≤ t ≤ 1000; 0 ≤ aij, bij ≤ 10; 1 ≤ itm; 1 ≤ jtn; 1 ≤ kt ≤ 109.

Output

For each t, output bitjtkt mod 1,000,000,007.

Sample Input

2 2 5
1 2
2 1
1 1
1 1
1 1 2
1 2 2
2 1 2
2 2 2
1 1 3

Sample Output

1
2
2
9
1

Hint

1,000,000,007 is a prime.

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator