时间限制：1秒　　内存限制：256M

---

【题目描述】

　　一张有向图有 \(N\) 个节点，小C同学从节点 0 出发，他必须恰好在 \(T\) 时刻到达节点 \(N-1\)。现在给出该有向图，你能告诉小C总共有多少种不同的路径吗？

【输入格式】

　　第一行包含两个整数，\(N\ T\)。接下来有 \(N\) 行，每行一个长度为 \(N\) 的字符串。第 \(i\) 行第 \(j\) 列为"0"表示从节点 \(i\) 到节点 \(j\) 没有边。为"1"到"9"表示从节点 \(i\) 到节点 \(j\) 需要耗费的时间。

【输出格式】

　　包含一个整数，可能的路径数，这个数可能很大，只需输出这个数除以 2009 的余数。

【输入输出样例1】

　Input

2 2
11
00

　Output

1

【输入输出样例2】

　Input

5 30
12045
07105
47805
12024
12345

　Output

852

【数据限制】

　　对于 \(30\%\) 的数据，\(2≤N≤5\)，\(1≤T≤30\)
　　对于 \(100\%\) 的数据，\(2≤N≤10\)，\(1≤T≤1000000000\)

【来源】

　　Mr.he**