求条

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 1000000009
int n,k;
struct matrix
{
    int p[105][105];
    matrix operator * (const matrix d) const
    {
        matrix g;
        memset(g.p,0,sizeof(g.p));
        for(int i = 1;i <= n;i++)
        {
            for(int j = 1;j <= n;j++)
            {
                for(int k = 1;k <= n;k++)
                {
                    g.p[i][j] += (d.p[i][k] * p[k][j]);
                    g.p[i][j] %= MOD;
                }
            }
        }
        return g;
    }
} p,l[65],ans;
void output(matrix r)
{
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            cout << r.p[i][j] << " ";
        }
        cout << endl;
    }
}
void read(matrix &p)
{
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            cin >> p.p[i][j];
        }
    }
}
void init(matrix &p,int l)
{
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            p.p[i][j] = l;
        }
    }
}
void ksm(matrix p)
{
    init(ans,1);
    init(l[0],1);
    while(k)
    {
    	if(k & 1) ans = ans * p;
    	p = p * p;
    	k >>= 1;
	}
}
signed main()
{
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
    cin >> n >> k;
    read(p);
    if(k == 1)
    {
        output(p);
        return 0;
    }
    ksm(p);
    output(ans);
    return 0;
}
/*
1 1
1 0

1 1
1 0


*/