Description

Original source: SCOI 2009

Windy is lost in a directed graph. The graph has $N$ nodes, and Windy starts at node $0$. He must arrive exactly at time $T$ at node $N-1$.

Given the directed graph, can you tell Windy how many different paths there are?

Note: Windy cannot linger at any node, and the time taken to traverse each directed edge is exactly the given time.

Input Format

The first line contains two integers, $N,T$;
The next $N$ lines each contain a string of length $N$. The $j$-th character in the $i$-th line is 0 if there is no edge from node $i$ to node $j`, or a digit from `1` to `9` representing the time required to traverse the edge from node $i$to node$j`.

Output Format

Output a single integer, the number of possible paths. This number may be very large, so only output the remainder when divided by $2009$.

Sample 1

$0\to 0\to 1$

2 2
11
00

1

Sample 2

5 30
12045
07105
47805
12024
12345

852

Data Range and Hints

For $30\%$ of the data, $2\le N\le 5,1\le T\le 30$;
For $100\%$ of the data, $2\le N\le 10,1\le T\le 10^9$.