You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

原题来自：SCOI 2009

Windy 在有向图中迷路了。 该有向图有 $N$ 个节点，Windy 从节点 $0$ 出发，他必须恰好在 $T$ 时刻到达节点 $N-1$。

现在给出该有向图，你能告诉 Windy 总共有多少种不同的路径吗？

注意：Windy 不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。

输入格式

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

输出格式

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

样例 1

2 2
11
00

1

$0\to 0\to 1$

5 30
12045
07105
47805
12024
12345

852

数据范围与提示

对于 $30\%$ 的数据，满足 $2\le N\le 5,1\le T\le 30$；
对于 $100\%$ 的数据，满足 $2\le N\le 10,1\le T\le 10^9$。