Problem G
State Transfer Matrix

Make a program that you can use for state transfer matrix problems in the rest of this module/problem set.

A state transfer matrix $A$ gives the number of ways to move from one state to another. For example if we have $5$ states then there are $a_{3,2}$ number of ways to move from state $3$ to state $2$. If this value is $0$ there is no way to move directly from state $3$ to state $2$.

Such a transfer matrix can be viewed as the adjacency matrix of a (not necessarily simple) directed graph. Then this is equivalent to asking for the number of directed paths from a legal starting state to a legal ending state which contains exactly $k$ edges.

Input

The first line of input contains three positive integers $n,m,k$. $n$ is the number of states and satisfies $n\le 20$. $m$ is the modulus the output should be output with respect to and satisfies $2\le m\le {10}^9+7$. $k$ is the number of transfers that should be made and satisfies $k\le {10}^{18}$. Next there are $n$ lines, each containing $n$ integers separated by spaces. These lines give the state transfer matrix, each value in the matrix is a non-negative single digit number. The next line gives the number $s$ og legal starting states, satisfying $1\le s\le n$. The line after gives $s$ different legal starting states. The next $2$ lines give the legal ending states in the same format. The states are represented with integers from $0$ to $n-1$.

Output

Print the number of ways to start in a legal state, make $k$ transitions according to the state transfer matrix and then end in a legal ending state. Print this value modulo $m$.

2 1000 10
1 1
1 0
1
1
2
0 1

89