Time Limits: 1000 ms Memory Limits: 65536 KB Detailed Limits

Description

windy在有向图中迷路了。
该有向图有 N 个节点,windy从节点 0 出发,他必须恰好在 T 时刻到达节点 N-1。
现在给出该有向图,你能告诉windy总共有多少种不同的路径吗?
注意:windy不能在某个节点逗留,且通过某有向边的时间严格为给定的时间。

Input

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

Output

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

Sample Input

2 2
11
00

Sample Output

1

Data Constraint

Hint

100%的数据,满足 2 <= N <= 10 ; 1 <= T <= 1000000000 。

Code

#include <bits/stdc++.h>
using namespace std;
int mod=2009;
int n,t;
struct pp{
int m[115][115];
}a;
int c;
inline pp mul(pp b,pp c)
{
pp t;
for(int i=1;i<=10*n;i++)
for(int j=1;j<=10*n;j++){
t.m[i][j]=0;
for(int k=1;k<=10*n;k++){
t.m[i][j]=(t.m[i][j]+(b.m[i][k]*c.m[k][j])%mod)%mod;
}
}
return t;
}
inline int fast(int x)
{
pp ans=a;
pp base=a;
while(x)
{
if(x&1)ans=mul(ans,base);
base=mul(base,base);
x=x>>1;
}
return ans.m[1][n];
}
int main()
{
cin>>n>>t;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=8;j++)
a.m[i+j*n][i+(j-1)*n]=1;
for(int j=1;j<=n;j++)
{
scanf("%1d",&c);
a.m[i][j+n*(c-1)]=1;
}
}
cout<<fast(t-1);
return 0;
}