Description

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.

Input Format

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 Format

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

2 2
11
00

1

5 30
12045
07105
47805
12024
12345

852

Hint

• 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