#include <algorithm> #include <iostream> #include <cstring> #include <iomanip> #include <cstdlib> #include <climits> #include <cstdio> #include <bitset> #include <string> #include <vector> #include <cctype> #include <stack> #include <queue> #include <deque> #include <cmath> #include <map> #include <set>
#define I inline #define fi first #define se second #define pb push_back #define MP make_pair #define PII pair<int , int> #define PSL pair<string , long long> #define PLL pair<long long , long long> #define all(x) (x).begin() , (x).end() #define copy(a , b) memcpy(a , b , sizeof(b)) #define clean(a , b) memset(a , b , sizeof(a)) #define rep(i , l , r) for (int i = (l); i <= (r); i ++) #define per(i , r , l) for (int i = (r); i >= (l); i --) #define PE(i , x) for(int i = head[x]; i; i = edge[i].last) #define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl
typedef long long ll; typedef unsigned long long ull;
template <class T> inline void read(T &x) { char c = getchar(), f = 0; x = 0; while (!isdigit(c)) f = (c == '-'), c = getchar(); while (isdigit(c)) x = x * 10 + c - '0', c = getchar(); x = f ? -x : x; }
using namespace std;
const int N = 10001; const int M = 100001; const int HA = 2009;
struct Matrix{ ll data[105][105]; };
Matrix operator * (const Matrix &A , const Matrix &B){ Matrix C; clean(C.data , 0); rep(i , 0 , 100){ rep(j , 0 , 100){ rep(k , 0 , 100){ C.data[i][j] += A.data[i][k] * B.data[k][j]; C.data[i][j] %= HA; } } } return C; }
Matrix Pow(Matrix A , ll k){ Matrix B; clean(B.data , 0); rep(i , 1 , 100) B.data[i][i] = 1; while(k){ if(k & 1) { B = B * A; } A = A * A; k >>= 1; } return B; }
char s[M];
Matrix A , ans;
int main() { #ifdef LOCAL freopen("try.in" , "r" , stdin); freopen("try1.out" , "w" , stdout); #endif ll n , t; read(n) , read(t); rep(i , 1 , n){ int now = (i - 1) * 9; rep(j , 1 , 8){ A.data[now + j][now + j + 1] = 1; } } rep(i , 1 , n){ scanf("%s" , s + 1); int now = (i - 1) * 9; rep(j , 1 , n){ if(s[j] == '0') continue; else{ int dis = (int)(s[j] - '0'); A.data[now + dis][(j - 1) * 9 + 1] = 1; } } } clean(ans.data , 0); rep(i , 1 , 10 * n) ans.data[i][i] = 1; ans = Pow(A , t); printf("%lld\n" , ans.data[1][(n - 1) * 9 + 1]);
return 0; }
|