P4159 [SCOI2009] Lost

windy got lost in a directed graph.

The directed graph has $n$ nodes, numbered from $1$ to $n$. windy starts from node $1$ and must arrive at node $n$ exactly at time $t$. Given the directed graph, can you tell windy how many different paths there are? The answer is taken modulo $2009$. Note: windy cannot wait at any node, and the time to traverse any directed edge is exactly the specified time.

The first line contains two integers, $n$ and $t$. Lines $2$ to $n+1$ each contain a string of length $n$. In line $(i+1)$, the $j$-th character $c_{i,j}$ is a digit. If it is $0$, there is no edge from node $i$ to node $j$; otherwise, the length of the edge from node $i$ to node $j$ is $c_{i,j}$.

Output a single integer: the answer modulo $2009$.

- Explanation for Sample Input/Output 1 The path is $1 \to 1 \to 2$. - Constraints - For $30\%$ of the testdata, $n \leq 5$, $t \leq 30$. - For $100\%$ of the testdata, $2 \leq n \leq 10$, $1 \leq t \leq 10^9$. Translated by ChatGPT 5