题号：NC50584
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld
题目描述
Windy在有向图中迷路了。该有向图有N个节点，Windy从节点0出发，他必须恰好在T时刻到达节点N-1。
现在给出该有向图，你能告诉Windy总共有多少种不同的路径吗？
注意：Windy不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。
现在给出该有向图，你能告诉Windy总共有多少种不同的路径吗？
注意：Windy不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。
输入描述:
第一行包含两个整数，N,T；
接下来有N行，每行一个长度为N的字符串。第i行第j列为0表示从节点i到节点j没有边，为1到9表示从节点i到节点j需要耗费的时间。
输出描述:
包含一个整数，可能的路径数，这个数可能很大，只需输出这个数除以2009的余数。
备注:
对于的数据，满足
；
对于的数据，满足
。