6725 - 迷路
时间限制 : 1 秒
内存限制 : 128 MB
Windy在有向图中迷路了。该有向图有N结点，Windy从结点0出发，他必须恰好在T时刻到达结点N-1。现在给出该有向图，你能够告诉Windy总共有多少种不同的路径吗？注意：Windy不能在某个结点逗留，且通过某有向边的时间严格为给定的时间。
输入
第一行包含两个整数N，T。接下来有N行，每行一个长度为N的字符串。第i行第j列为‘0’表示从结点i到结点j没有边。为‘1’到‘9’表示从结点i到结点j需要耗费的时间。
输出
包含一个整数，可能的路径数，这个数可能很大，只需输出这个数除以2009的余数。
样例
输入
2 2 11 00
输出
1
输入
5 30 12045 07105 47805 12024 12345
输出
852
提示
【数据规模】
来源
一本通