题目背景

windy 在有向图中迷路了。

题目描述

该有向图有$n$个节点，节点从$1$至$n$编号，windy 从节点$1$出发，他必须恰好在$t$时刻到达节点$n$。

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

答案对$2009$取模。

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

输入输出格式

输入格式

第一行包含两个整数，分别代表$n$和$t$。

第$2$到第$(n + 1)$行，每行一个长度为$n$的字符串，第$(i + 1)$行的第$j$个字符$c_{i, j}$是一个数字字符，若为$0$，则代表节点$i$到节点$j$无边，否则代表节点$i$到节点$j$的边的长度为$c_{i, j}$。

输出格式

输出一行一个整数代表答案对$2009$取模的结果。

输入输出样例

输入样例 #1

2 2
11
00

输出样例 #1

1

输入样例 #2

5 30
12045
07105
47805
12024
12345

输出样例 #2

852

说明/提示

样例输入输出 1 解释

路径为$1 \to 1 \to 2$。

数据规模与约定

• 对于$30\%$的数据，保证$n \leq 5$，$t \leq 30$。
• 对于$100\%$的数据，保证$2 \leq n \leq 10$，$1 \leq t \leq 10^9$。