原題來自：SCOI 2009

Windy 在有向圖中迷路了。 該有向圖有 N 個節(jié)點(diǎn)，Windy 從節(jié)點(diǎn) 0 出發(fā)，他必須恰好在 T 時(shí)刻到達(dá)節(jié)點(diǎn) N?1。

現(xiàn)在給出該有向圖，你能告訴 Windy 總共有多少種不同的路徑嗎？

注意：Windy 不能在某個節(jié)點(diǎn)逗留，且通過某有向邊的時(shí)間嚴(yán)格為給定的時(shí)間。

第一行包含兩個整數(shù)，N,T；

接下來有 N 行，每行一個長度為 N 的字符串。第 i 行第 j 列為 0 表示從節(jié)點(diǎn) i 到節(jié)點(diǎn) j 沒有邊，為 1 到 9 表示從節(jié)點(diǎn) i 到節(jié)點(diǎn) j 需要耗費(fèi)的時(shí)間。

包含一個整數(shù)，可能的路徑數(shù)，這個數(shù)可能很大，只需輸出這個數(shù)除以 2009 的余數(shù)。

樣例說明 1

0→0→1
樣例輸入 2

5 30
12045
07105
47805
12024
12345
樣例輸出 2

852
數(shù)據(jù)范圍與提示：

對于 30% 的數(shù)據(jù)，滿足 2≤N≤5,1≤T≤30；

對于 100% 的數(shù)據(jù)，滿足 2≤N≤10,1≤T≤10⁹ 。

信息學(xué)一本通 數(shù)學(xué)