Problem A
State Transfer Matrix
Languages
en
is
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 \leq 20$. $m$ is the modulus the output should be output with respect to and satisfies $2 \leq m \leq 10^9 + 7$. $k$ is the number of transfers that should be made and satisfies $k \leq 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 \leq s \leq 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$.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 1000 10 1 1 1 0 1 1 2 0 1 |
89 |
