2927: 「一本通 6.5 练习 3」迷路

Memory Limit:512 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:9 Solved:8

Description

原题来自:SCOI 2009

Windy 在有向图中迷路了。 该有向图有 NNN 个节点,Windy 从节点 000 出发,他必须恰好在 TTT 时刻到达节点 N−1N-1N1

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

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

Input

第一行包含两个整数,N,TN,TN,T
接下来有 NNN 行,每行一个长度为 NNN 的字符串。第 iii 行第 jjj 列为 0 表示从节点 iii 到节点 jjj 没有边,为 19 表示从节点 iii 到节点 jjj 需要耗费的时间。

Output

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

HINT

样例输入 1

2 2
11
00

样例输出 1

1

样例说明 1

0→0→10 o 0 o 1001

样例输入 2

5 30
12045
07105
47805
12024
12345

样例输出 2

852

对于 30%30\%30% 的数据,满足 2≤N≤5,1≤T≤302le Nle 5,1le Tle 302N5,1T30
对于 100%100\%100% 的数据,满足 2≤N≤10,1≤T≤1092le Nle 10,1le Tle 10^92N10,1T109

加入题单

上一题 下一题 算法标签: