stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;



typedef long long llt;



const int MaxN = 50 + 5;

const llt Mod = 1e9 + 7;



struct Matrix {

  llt mat[MaxN][MaxN];

  Matrix() {

    memset(mat, 0, sizeof mat);

  }

};



int N; llt K;

Matrix G;



inline Matrix operator * (Matrix A, Matrix B) {

  Matrix C;

  for (int i = 1; i <= N; ++i)

    for (int j = 1; j <= N; ++j) {

      for (int k = 1; k <= N; ++k)

        C.mat[i][j] = (C.mat[i][j] + A.mat[i][k] * B.mat[k][j]) % Mod;

    }

  return C;

}



inline Matrix operator ^ (Matrix low, llt high) {

  Matrix res;

  for (int i = 1; i <= N; ++i) res.mat[i][i] = 1;

  while (high) {

    if (high & 1) res = res * low;

    high >>= 1;

    low = low * low;

  }

  return res;

}



void init() {

  scanf("%d %lld", &N, &K);

  for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j)

    scanf("%lld", &G.mat[i][j]);

}



void solve() {

  G = G ^ K;

  llt res = 0;

  for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j)

    res = (res + G.mat[i][j]) % Mod;

  cout << res << endl;

}



int main() {

  init();

  solve();

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.5048614218709195x):
#include <cstdio>

#include <cstring>



const int MaxN = 50;

const int Mod = 1000000007;



int N;

long long K;



inline int add(int x, int y) { return (x += y) >= Mod ? x - Mod : x; }

inline int sub(int x, int y) { return (x -= y) < 0 ? x + Mod : x; }

inline int mul(int x, int y) { return 1LL * x * y % Mod; }



struct Matrix {

  int mat[MaxN][MaxN];



  Matrix() {

    memset(mat, 0, sizeof mat);

  }



  inline friend Matrix operator + (const Matrix &a, const Matrix &b) {

    Matrix c;

    for (int i = 0; i < N; ++i)

      for (int j = 0; j < N; ++j)

        c.mat[i][j] = add(a.mat[i][j], b.mat[i][j]);

    return c;

  }



  inline friend Matrix operator * (const Matrix &a, const Matrix &b) {

    Matrix c;

    for (int i = 0; i < N; ++i)

      for (int j = 0; j < N; ++j) {

        int x = 0;

        for (int k = 0; k < N; ++k)

          x = add(x, mul(a.mat[i][k], b.mat[k][j]));

        c.mat[i][j] = x;

      }

    return c;

  }



  inline friend Matrix operator ^ (Matrix low, long long high) {

    Matrix res;

    for (int i = 0; i < N; ++i) res.mat[i][i] = 1;

    while (high) {

      if (high & 1) res = res * low;

      high >>= 1;

      low = low * low;

    }

    return res;

  }

};

Matrix G;



void init() {

  scanf("%d %lld", &N, &K);

  for (int i = 0; i < N; ++i)

    for (int j = 0; j < N; ++j)

      scanf("%d", &G.mat[i][j]);

}



void solve() {

  G = G ^ K;

  int ans = 0;

  for (int i = 0; i < N; ++i)

    for (int j = 0; j < N; ++j)

      ans = add(ans, G.mat[i][j]);

  printf("%d\n", ans);

}



int main() {

  init();

  solve();

  return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

 

#define ll long long

#define X first

#define Y second

#define MP make_pair

 

using namespace std;



const int N = 123;

const ll mod = 1e9 + 7;             



int n;

struct mtx{

	ll a[N][N], len = n;

	mtx(){

		memset(a, 0, sizeof(a));

	}

	void operator *= (mtx b){

		int res[N][N];

		memset(res, 0, sizeof(res));

		for(int i = 1;i <= len;i++){

			for(int j = 1;j <= len;j++){

				for(int k = 1;k <= len;k++){

					res[i][j] = (res[i][j] + a[i][k] * b.a[k][j]) % mod;

				}

			}

		}

		for(int i = 1;i <= len;i++){

			for(int j = 1;j <= len;j++){

				a[i][j] = res[i][j];

			}

		}

	}

};



mtx bin_pow(mtx x, ll y){

	mtx res;

	for(int i = 1;i <= n;i++){

			res.a[i][i] = 1;

	}

    

	while(y){

		if(y & 1LL)

			res *= x;

		

	/*	for(int i = 1;i <= n;i++){	

			for(int j = 1;j <= n;j++){

				cout << res.a[i][j] << " ";

	    	}

			cout << "\n";

		}

	*/	

		x *= x;

		y >>= 1LL;

	}

	return res;

}

   

int main () {

	ios::sync_with_stdio(0);

	cin.tie(0);

	cout.tie(0);



	ll k;

	cin >> n >> k;

	mtx z;

	for(int i = 1;i <= n;i++)

		for(int j = 1;j <= n;j++)

			cin >> z.a[i][j];

	//z *= z;

	z = bin_pow(z, k);

	ll res = 0;

	for(int i = 1;i <= n;i++){	

		for(int j = 1;j <= n;j++){

		//	cout << z.a[i][j] << " ";

			res += z.a[i][j], res %= mod;

	    }

		//cout << "\n";

	}

	cout << res;

}

// Faster C++ solution for the same problem (measured speedup: 1.655257796494628x):
#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=55,mod=1e9+7;

int n,k;

struct mat

{

	int a[N][N];

	void init1()

	{

		for(int i=1;i<=n;i++)

			for(int j=1;j<=n;j++)

				a[i][j]=0;

	}

	void init2()

	{

		init1();

		for(int i=1;i<=n;i++)

			a[i][i]=1;

	}

}a,ans;

mat mul(mat a,mat b)

{

	mat c;

	c.init1();

	for(int i=1;i<=n;i++)

		for(int k=1;k<=n;k++)

			for(int j=1;j<=n;j++)

				c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j]%mod)%mod;

	return c;

}

main()

{

	ios::sync_with_stdio(false);

	cin>>n>>k;

	for(int i=1;i<=n;i++)

		for(int j=1;j<=n;j++)

			cin>>a.a[i][j];

	ans.init2();

	while(k)

	{

		if(k&1) 

			ans=mul(ans,a);

		a=mul(a,a);

		k>>=1;

	}

	int sum=0;

	for(int i=1;i<=n;i++)

		for(int j=1;j<=n;j++)

			sum=(sum+ans.a[i][j])%mod;

	cout<<sum<<endl;

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

 

#define ll long long

#define X first

#define Y second

#define MP make_pair

 

using namespace std;



const int N = 123;

const ll mod = 1e9 + 7;             



int n;

struct mtx{

	ll a[N][N], len = n;

	mtx(){

		memset(a, 0, sizeof(a));

	}

	void operator *= (mtx b){

		int res[N][N];

		memset(res, 0, sizeof(res));

		for(int i = 1;i <= len;i++){

			for(int j = 1;j <= len;j++){

				for(int k = 1;k <= len;k++){

					res[i][j] = (res[i][j] + a[i][k] * b.a[k][j]) % mod;

				}

			}

		}

		for(int i = 1;i <= len;i++){

			for(int j = 1;j <= len;j++){

				a[i][j] = res[i][j];

			}

		}

	}

};



mtx bin_pow(mtx x, ll y){

	mtx res;

	for(int i = 1;i <= n;i++){

			res.a[i][i] = 1;

	}

    

	while(y){

		if(y & 1LL)

			res *= x;

		

	/*	for(int i = 1;i <= n;i++){	

			for(int j = 1;j <= n;j++){

				cout << res.a[i][j] << " ";

	    	}

			cout << "\n";

		}

	*/	

		x *= x;

		y >>= 1LL;

	}

	return res;

}

   

int main () {

	ios::sync_with_stdio(0);

	cin.tie(0);

	cout.tie(0);



	ll k;

	cin >> n >> k;

	mtx z;

	for(int i = 1;i <= n;i++)

		for(int j = 1;j <= n;j++)

			cin >> z.a[i][j];

	//z *= z;

	z = bin_pow(z, k);

	ll res = 0;

	for(int i = 1;i <= n;i++){	

		for(int j = 1;j <= n;j++){

		//	cout << z.a[i][j] << " ";

			res += z.a[i][j], res %= mod;

	    }

		//cout << "\n";

	}

	cout << res;

}

// Faster C++ solution for the same problem (measured speedup: 1.889798975999122x):
#include <bits/stdc++.h>

using namespace std;

#define mod 1000000007

#define ll long long

ll n, k;

struct Matrix {

    ll mat[50][50];

    void clear() { memset(mat, 0, sizeof(mat)); }

    void reset(int n) {

        clear();

        for (int i = 0; i < n; i++) mat[i][i] = 1;

    }

} a;

Matrix MatrixMul(Matrix x, Matrix y) {

    Matrix a;

    a.clear();

    for (int i = 0; i < n; i++)

        for (int k = 0; k < n; k++)

            for (int j = 0; j < n; j++)

                a.mat[i][j] = (a.mat[i][j] + x.mat[i][k] * y.mat[k][j]) % mod;

    return a;

}

ll MatrixQpow(Matrix a, ll P) {

    Matrix s;

    s.reset(n);

    while (P) {

        if (P & 1) s = MatrixMul(s, a);

        a = MatrixMul(a, a), P >>= 1;

    }

    ll sum = 0;

    for (int i = 0; i < n; i++)

        for (int j = 0; j < n; j++) sum = (sum + s.mat[i][j]) % mod;

    return sum;

}

int main() {

    scanf("%lld%lld", &n, &k);

    for (int i = 0; i < n; i++)

        for (int j = 0; j < n; j++) scanf("%lld", &a.mat[i][j]);

    printf("%lld\n", MatrixQpow(a, k));

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

 

#define ll long long

#define X first

#define Y second

#define MP make_pair

 

using namespace std;



const int N = 123;

const ll mod = 1e9 + 7;             



int n;

struct mtx{

	ll a[N][N], len = n;

	mtx(){

		memset(a, 0, sizeof(a));

	}

	void operator *= (mtx b){

		int res[N][N];

		memset(res, 0, sizeof(res));

		for(int i = 1;i <= len;i++){

			for(int j = 1;j <= len;j++){

				for(int k = 1;k <= len;k++){

					res[i][j] = (res[i][j] + a[i][k] * b.a[k][j]) % mod;

				}

			}

		}

		for(int i = 1;i <= len;i++){

			for(int j = 1;j <= len;j++){

				a[i][j] = res[i][j];

			}

		}

	}

};



mtx bin_pow(mtx x, ll y){

	mtx res;

	for(int i = 1;i <= n;i++){

			res.a[i][i] = 1;

	}

    

	while(y){

		if(y & 1LL)

			res *= x;

		

	/*	for(int i = 1;i <= n;i++){	

			for(int j = 1;j <= n;j++){

				cout << res.a[i][j] << " ";

	    	}

			cout << "\n";

		}

	*/	

		x *= x;

		y >>= 1LL;

	}

	return res;

}

   

int main () {

	ios::sync_with_stdio(0);

	cin.tie(0);

	cout.tie(0);



	ll k;

	cin >> n >> k;

	mtx z;

	for(int i = 1;i <= n;i++)

		for(int j = 1;j <= n;j++)

			cin >> z.a[i][j];

	//z *= z;

	z = bin_pow(z, k);

	ll res = 0;

	for(int i = 1;i <= n;i++){	

		for(int j = 1;j <= n;j++){

		//	cout << z.a[i][j] << " ";

			res += z.a[i][j], res %= mod;

	    }

		//cout << "\n";

	}

	cout << res;

}

// Faster C++ solution for the same problem (measured speedup: 1.9746397162080094x):
#include <bits/stdc++.h>

 

using namespace std;

const int maxn = 50 + 1, mod = 1e9 + 7;

 

int n;

 

struct matrix{

    int c[maxn][maxn];

    void init()

    {

        for(int i=1; i<=n; ++i)

            for(int j=1; j<=n; ++j) c[i][j] = 0;

    }

};

 

matrix cs;

long long k;

 

matrix mul(matrix a, matrix b)

{

    matrix t; t.init();

    for(int i=1; i<=n; ++i)

        for(int j=1; j<=n; ++j) 

            for(int k=1; k<=n; ++k) 

        t.c[i][j] = (t.c[i][j] + (1LL*a.c[i][k]*b.c[k][j]) % mod) % mod;

    return t;

}

matrix power(long long b)

{

    if (b == 1) return cs;

    matrix t = power(b/2);

    t = mul(t, t);

    if (b&1) t = mul(t, cs);

    return t;

}

 

int main()

{

    cin >> n >> k;

    for(int i=1; i<=n; ++i)

        for(int j=1; j<=n; ++j) cin >> cs.c[i][j];

    long long ans = 0;

    matrix a = power(k);

    for(int i=1; i<=n; ++i)

        for(int j=1; j<=n; ++j) ans = (ans + a.c[i][j]) % mod;

    cout << ans;

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=55,mod=1e9+7;

int n,k;

struct mat

{

	int a[N][N];

	void init1()

	{

		for(int i=1;i<=n;i++)

			for(int j=1;j<=n;j++)

				a[i][j]=0;

	}

	void init2()

	{

		init1();

		for(int i=1;i<=n;i++)

			a[i][i]=1;

	}

}a,ans;

mat mul(mat a,mat b)

{

	mat c;

	c.init1();

	for(int i=1;i<=n;i++)

		for(int k=1;k<=n;k++)

			for(int j=1;j<=n;j++)

				c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j]%mod)%mod;

	return c;

}

main()

{

	ios::sync_with_stdio(false);

	cin>>n>>k;

	for(int i=1;i<=n;i++)

		for(int j=1;j<=n;j++)

			cin>>a.a[i][j];

	ans.init2();

	while(k)

	{

		if(k&1) 

			ans=mul(ans,a);

		a=mul(a,a);

		k>>=1;

	}

	int sum=0;

	for(int i=1;i<=n;i++)

		for(int j=1;j<=n;j++)

			sum=(sum+ans.a[i][j])%mod;

	cout<<sum<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.1929499564295922x):
#include <bits/stdc++.h>

 

using namespace std;

const int maxn = 50 + 1, mod = 1e9 + 7;

 

int n;

 

struct matrix{

    int c[maxn][maxn];

    void init()

    {

        for(int i=1; i<=n; ++i)

            for(int j=1; j<=n; ++j) c[i][j] = 0;

    }

};

 

matrix cs;

long long k;

 

matrix mul(matrix a, matrix b)

{

    matrix t; t.init();

    for(int i=1; i<=n; ++i)

        for(int j=1; j<=n; ++j) 

            for(int k=1; k<=n; ++k) 

        t.c[i][j] = (t.c[i][j] + (1LL*a.c[i][k]*b.c[k][j]) % mod) % mod;

    return t;

}

matrix power(long long b)

{

    if (b == 1) return cs;

    matrix t = power(b/2);

    t = mul(t, t);

    if (b&1) t = mul(t, cs);

    return t;

}

 

int main()

{

    cin >> n >> k;

    for(int i=1; i<=n; ++i)

        for(int j=1; j<=n; ++j) cin >> cs.c[i][j];

    long long ans = 0;

    matrix a = power(k);

    for(int i=1; i<=n; ++i)

        for(int j=1; j<=n; ++j) ans = (ans + a.c[i][j]) % mod;

    cout << ans;

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

#define mod 1000000007

#define ll long long

ll n, k;

struct Matrix {

    ll mat[50][50];

    void clear() { memset(mat, 0, sizeof(mat)); }

    void reset(int n) {

        clear();

        for (int i = 0; i < n; i++) mat[i][i] = 1;

    }

} a;

Matrix MatrixMul(Matrix x, Matrix y) {

    Matrix a;

    a.clear();

    for (int i = 0; i < n; i++)

        for (int k = 0; k < n; k++)

            for (int j = 0; j < n; j++)

                a.mat[i][j] = (a.mat[i][j] + x.mat[i][k] * y.mat[k][j]) % mod;

    return a;

}

ll MatrixQpow(Matrix a, ll P) {

    Matrix s;

    s.reset(n);

    while (P) {

        if (P & 1) s = MatrixMul(s, a);

        a = MatrixMul(a, a), P >>= 1;

    }

    ll sum = 0;

    for (int i = 0; i < n; i++)

        for (int j = 0; j < n; j++) sum = (sum + s.mat[i][j]) % mod;

    return sum;

}

int main() {

    scanf("%lld%lld", &n, &k);

    for (int i = 0; i < n; i++)

        for (int j = 0; j < n; j++) scanf("%lld", &a.mat[i][j]);

    printf("%lld\n", MatrixQpow(a, k));

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.0448940555510846x):
#include <bits/stdc++.h>

 

using namespace std;

const int maxn = 50 + 1, mod = 1e9 + 7;

 

int n;

 

struct matrix{

    int c[maxn][maxn];

    void init()

    {

        for(int i=1; i<=n; ++i)

            for(int j=1; j<=n; ++j) c[i][j] = 0;

    }

};

 

matrix cs;

long long k;

 

matrix mul(matrix a, matrix b)

{

    matrix t; t.init();

    for(int i=1; i<=n; ++i)

        for(int j=1; j<=n; ++j) 

            for(int k=1; k<=n; ++k) 

        t.c[i][j] = (t.c[i][j] + (1LL*a.c[i][k]*b.c[k][j]) % mod) % mod;

    return t;

}

matrix power(long long b)

{

    if (b == 1) return cs;

    matrix t = power(b/2);

    t = mul(t, t);

    if (b&1) t = mul(t, cs);

    return t;

}

 

int main()

{

    cin >> n >> k;

    for(int i=1; i<=n; ++i)

        for(int j=1; j<=n; ++j) cin >> cs.c[i][j];

    long long ans = 0;

    matrix a = power(k);

    for(int i=1; i<=n; ++i)

        for(int j=1; j<=n; ++j) ans = (ans + a.c[i][j]) % mod;

    cout << ans;

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=55,mod=1e9+7;

int n,k;

struct mat

{

	int a[N][N];

	void init1()

	{

		for(int i=1;i<=n;i++)

			for(int j=1;j<=n;j++)

				a[i][j]=0;

	}

	void init2()

	{

		init1();

		for(int i=1;i<=n;i++)

			a[i][i]=1;

	}

}a,ans;

mat mul(mat a,mat b)

{

	mat c;

	c.init1();

	for(int i=1;i<=n;i++)

		for(int k=1;k<=n;k++)

			for(int j=1;j<=n;j++)

				c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j]%mod)%mod;

	return c;

}

main()

{

	ios::sync_with_stdio(false);

	cin>>n>>k;

	for(int i=1;i<=n;i++)

		for(int j=1;j<=n;j++)

			cin>>a.a[i][j];

	ans.init2();

	while(k)

	{

		if(k&1) 

			ans=mul(ans,a);

		a=mul(a,a);

		k>>=1;

	}

	int sum=0;

	for(int i=1;i<=n;i++)

		for(int j=1;j<=n;j++)

			sum=(sum+ans.a[i][j])%mod;

	cout<<sum<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.031576205550395x):
/*

Luis Henrique Morelli

Walk

https://atcoder.jp/contests/dp/tasks/dp_r

10/09/2020

*/



#include <bits/stdc++.h>



#define MAX 50

#define MOD 1000000007



using namespace std;



void multiplyMatrix(int N, long long a[][MAX], long long b[][MAX]){

    long long c[MAX][MAX];



    for(int i = 0; i < N; i++){

        for(int j = 0; j < N; j++){

            c[i][j] = 0;

            

            for(int k = 0; k < N; k++){

                c[i][j] = (c[i][j] % MOD + (a[i][k] % MOD * b[k][j] % MOD) % MOD) % MOD;

            }

        }

    }



    for(int i = 0; i < N; i++){

        for(int j = 0; j < N; j++){

            b[i][j] = c[i][j];

        }

    }

}



long long matrixPower(int N, long long g[][MAX], long long K){

    long long paths[MAX][MAX];



    for(int i = 0; i < N; i++){

        for(int j = 0; j < N; j++){

            if(i != j){

                paths[i][j] = 0;

            }

        }



        paths[i][i] = 1;

    }



    while(K > 0){

        if(K % 2 != 0){

            multiplyMatrix(N, g, paths);

        }



        multiplyMatrix(N, g, g);



        K /= 2;

    }



    long long totalPaths;



    totalPaths = 0;



    for(int i = 0; i < N; i++){

        for(int j = 0; j < N; j++){

            totalPaths = (totalPaths % MOD + paths[i][j] % MOD) % MOD; 

        }

    }



    return totalPaths % MOD;

}



int main(){

    ios::sync_with_stdio(0);

    cin.tie(0);

   

    int N;

    long long K;



    cin >> N >> K;



    long long adjMatrix[MAX][MAX];



    for(int i = 0 ; i < N; i++){

        for(int j = 0; j < N; j++){

           cin >> adjMatrix[i][j];

        }

    }



    cout << matrixPower(N, adjMatrix, K) << "\n";

    

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

#define mod 1000000007

#define ll long long

ll n, k;

struct Matrix {

    ll mat[50][50];

    void clear() { memset(mat, 0, sizeof(mat)); }

    void reset(int n) {

        clear();

        for (int i = 0; i < n; i++) mat[i][i] = 1;

    }

} a;

Matrix MatrixMul(Matrix x, Matrix y) {

    Matrix a;

    a.clear();

    for (int i = 0; i < n; i++)

        for (int k = 0; k < n; k++)

            for (int j = 0; j < n; j++)

                a.mat[i][j] = (a.mat[i][j] + x.mat[i][k] * y.mat[k][j]) % mod;

    return a;

}

ll MatrixQpow(Matrix a, ll P) {

    Matrix s;

    s.reset(n);

    while (P) {

        if (P & 1) s = MatrixMul(s, a);

        a = MatrixMul(a, a), P >>= 1;

    }

    ll sum = 0;

    for (int i = 0; i < n; i++)

        for (int j = 0; j < n; j++) sum = (sum + s.mat[i][j]) % mod;

    return sum;

}

int main() {

    scanf("%lld%lld", &n, &k);

    for (int i = 0; i < n; i++)

        for (int j = 0; j < n; j++) scanf("%lld", &a.mat[i][j]);

    printf("%lld\n", MatrixQpow(a, k));

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.6553301243334064x):
/*

Luis Henrique Morelli

Walk

https://atcoder.jp/contests/dp/tasks/dp_r

10/09/2020

*/



#include <bits/stdc++.h>



#define MAX 50

#define MOD 1000000007



using namespace std;



void multiplyMatrix(int N, long long a[][MAX], long long b[][MAX]){

    long long c[MAX][MAX];



    for(int i = 0; i < N; i++){

        for(int j = 0; j < N; j++){

            c[i][j] = 0;

            

            for(int k = 0; k < N; k++){

                c[i][j] = (c[i][j] % MOD + (a[i][k] % MOD * b[k][j] % MOD) % MOD) % MOD;

            }

        }

    }



    for(int i = 0; i < N; i++){

        for(int j = 0; j < N; j++){

            b[i][j] = c[i][j];

        }

    }

}



long long matrixPower(int N, long long g[][MAX], long long K){

    long long paths[MAX][MAX];



    for(int i = 0; i < N; i++){

        for(int j = 0; j < N; j++){

            if(i != j){

                paths[i][j] = 0;

            }

        }



        paths[i][i] = 1;

    }



    while(K > 0){

        if(K % 2 != 0){

            multiplyMatrix(N, g, paths);

        }



        multiplyMatrix(N, g, g);



        K /= 2;

    }



    long long totalPaths;



    totalPaths = 0;



    for(int i = 0; i < N; i++){

        for(int j = 0; j < N; j++){

            totalPaths = (totalPaths % MOD + paths[i][j] % MOD) % MOD; 

        }

    }



    return totalPaths % MOD;

}



int main(){

    ios::sync_with_stdio(0);

    cin.tie(0);

   

    int N;

    long long K;



    cin >> N >> K;



    long long adjMatrix[MAX][MAX];



    for(int i = 0 ; i < N; i++){

        for(int j = 0; j < N; j++){

           cin >> adjMatrix[i][j];

        }

    }



    cout << matrixPower(N, adjMatrix, K) << "\n";

    

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;





int main() {

    int n,q,a,b,p,x;

    cin >> n >> q;

    vector<vector<int>> G(n);

    int c[200010]={0};

    for (int i=0;i<n-1;i++) {

        cin >> a >> b;

        a--;

        b--;

        G[a].push_back(b);

        G[b].push_back(a);

    }

    for (int j=0;j<q;j++) {

        cin >> p >> x;

        c[p-1]+=x;

    }

    vector<bool> flag(n); 

    queue<int> qu;

    int ans[200010]={0};

    qu.push(0);

    ans[0]=c[0];

    while (qu.size()>0) {

        int now = qu.front();

        qu.pop();

        for (int i=0;i<G[now].size();i++) {

            int next = G[now][i];

            if (flag[next]!=true) {

                ans[next]=c[next]+ans[now];

                qu.push(G[now][i]);

            }

        }

        flag[now]=true;

    }

    for (int i=0;i<n;i++) {

        cout << ans[i];

        if (i!=n-1) cout << ' ';

        else cout << endl;

    }

}

// Faster C++ solution for the same problem (measured speedup: 2.5736792304667926x):
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

#define repr(i,a,b) for(int i=a;i<b;i++)

#define rep(i,n) for(int i=0;i<n;i++)

#define invrepr(i,a,b) for(int i=b-1;i>=a;i--)

#define invrep(i,n) invrepr(i,0,n)

#define repitr(itr,a) for(auto itr=a.begin();itr!=a.end();++itr)

const int MOD=1e9+7;





int main() {

    ios_base::sync_with_stdio(false);



    int n,k;

    cin >> n >> k;

    vector<vector<int>> r(n);

    rep(i,n-1) {

        int a,b;

        cin >> a >> b;

        r[a-1].push_back(b-1);

        r[b-1].push_back(a-1);

    }

    vector<int> s(n);

    rep(i,k) {

        int p,x;

        cin >> p >> x;

        s[p-1]+=x;

    }

    queue<int> q;

    vector<int> cost(n,-1);

    q.push(0);

    cost[0]=0;

    while (!q.empty()) {

        int now=q.front();

        q.pop();

        rep(i,r[now].size()) {

            int next=r[now][i];

            if (cost[next]==-1) {

                s[next]+=s[now];

                cost[next]=cost[now]+1;

                q.push(next);

            }

        }

    }

    rep(i,n) cout << s[i] << ' ';

    cout << endl;





    return 0;   

}
// Slower C++ solution:
#include <vector>

#include <iostream>

using namespace std;

vector<int> graph[200010];

vector<int> ans(200010, 0);



void dfs(int v, int p=-1) {

  for(int u: graph[v]) {

    if(u == p) continue;

    else ans[u] += ans[v];

    dfs(u, v);

  }

}



int main() {

  int N, Q; cin >> N >> Q;

  for(int i = 0; i < N-1; ++i) {

    int a, b; cin >> a >> b; a--, b--;

    graph[a].push_back(b);

    graph[b].push_back(a);

  }



  for(int i = 0; i < Q; i++) {

    int p, x; cin >> p >> x; p--;

    ans[p] += x;

  }



  dfs(0);



  for(int i = 0; i < N; i++) {

    cout << ans[i];

    if(i != N-1) cout << " ";

    else cout << endl;

  }

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.143649160200994x):
#include <iostream>

#include <iomanip>

#include <algorithm>

#include <vector>

#include <queue>

#include <cmath>

#include <map>

#include <set>

#include <deque>

#define rep(i, n) for(int i = 0; i < (n); i++)

using namespace std;

typedef long long ll;



vector<int> to[200010];

vector<int> ans;



void dfs(int v, int p=-1) {

  for(int u: to[v]) {

    if(u == p) continue;

    ans[u] += ans[v];

    dfs(u, v);

  }

}



int main() {

  int n, q; cin >> n >> q;

  rep(i, n-1) {

    int a, b; cin >> a >> b;

    --a, --b;

    to[a].push_back(b);

    to[b].push_back(a);

  }

  ans.resize(n);

  rep(i, q) {

    int p, x; cin >> p >> x;

    p--;

    ans[p] += x;

  }



  dfs(0);



  rep(i, n) {

    if(i) cout << " ";

    cout << ans[i];

  }

  cout << endl;



  return 0;

}