stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<bits/stdc++.h>

#define ll long long

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

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

using namespace std;

ll ans;

ll n,x,y;

ll a[100100],b[100100],c[100100];

inline ll read()

{

    ll x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

    return x*f;

}

int main()

{

	n=read();

	For(i,1,n)a[i]=read();

	For(i,1,n)b[i]=read();

	For(i,1,n)c[i]=-read();

	sort(a+1,a+n+1);

	sort(b+1,b+n+1);

	sort(c+1,c+n+1);

	For(i,1,n)c[i]=-c[i];

	x=0;y=n;

	For(i,1,n)

	{

		while(a[x+1]<b[i]&&x<n)x++;

		while(c[y]<=b[i]&&y>0)y--;

		ans+=(x*y);

	}

	cout<<ans<<endl;

	return 0;

}

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

#include <cstdio>

#include <algorithm>

using namespace std;



static const int N = 1e5 + 10;

int n;

int a[N], b[N], c[N], cnt1[N], cnt2[N];



int main ()

{

	scanf ("%d", &n);

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

		scanf ("%d", &a[i]);

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

		scanf ("%d", &b[i]);

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

		scanf ("%d", &c[i]);

	sort (a + 1, a + n + 1);

	sort (b + 1, b + n + 1);

	sort (c + 1, c + n + 1);

	int k = 1;

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

	{

		for (; c[k] <= b[i] && k <= n ;)

			++k;

		cnt1[i] = n - k + 1;

	}

	k = 1;

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

	{

		for (; a[k] < b[i] && k <= n ;)

			++k;

		cnt2[i] = k - 1;

	}

	long long ans = 0;

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

		ans += (long long)cnt1[i] * cnt2[i];

	printf ("%lld", ans);

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

#include<algorithm>

using namespace std;

int n,A[100010],B[100010],C[100010],D[100010],i,j;

long long E[100010],sum=0;

int main(){

    cin>>n;

    for(i=1;i<=n;i++) cin>>A[i];

    for(i=1;i<=n;i++) cin>>B[i];

    for(i=1;i<=n;i++) cin>>C[i];

    sort(A+1,A+1+n);

    sort(B+1,B+1+n);

    sort(C+1,C+1+n);

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

        D[i]=C+1+n-upper_bound(C+1,C+1+n,B[i]);

        E[i]=E[i-1]+D[i];

    }

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

        if(B+1+n-upper_bound(B+1,B+1+n,A[i])>0){

            sum+=E[n]-E[upper_bound(B+1,B+1+n,A[i])-B-1];

        }

    }

    cout<<sum<<endl;

    return 0;

}

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

#include <cstdio>

#include <algorithm>

using namespace std;



static const int N = 1e5 + 10;

int n;

int a[N], b[N], c[N], cnt1[N], cnt2[N];



int main ()

{

	scanf ("%d", &n);

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

		scanf ("%d", &a[i]);

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

		scanf ("%d", &b[i]);

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

		scanf ("%d", &c[i]);

	sort (a + 1, a + n + 1);

	sort (b + 1, b + n + 1);

	sort (c + 1, c + n + 1);

	int k = 1;

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

	{

		for (; c[k] <= b[i] && k <= n ;)

			++k;

		cnt1[i] = n - k + 1;

	}

	k = 1;

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

	{

		for (; a[k] < b[i] && k <= n ;)

			++k;

		cnt2[i] = k - 1;

	}

	long long ans = 0;

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

		ans += (long long)cnt1[i] * cnt2[i];

	printf ("%lld", ans);

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

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N=1e6+10;

int n,m,a[4][N];

ll ans,cnt[N];



 

int main()

{

//	freopen("in.in","r",stdin);

//	freopen("out.out","w",stdout);

	scanf("%d",&n);

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

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

		scanf("%d",&a[i][j]);

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

		sort(a[i]+1,a[i]+n+1);

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

	{

		while(a[1][i]<a[2][j]&&i<=n) i++;

		cnt[j]=i-1;

	}

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

//		printf("cnt=%d\n",cnt[i]);

//改用前缀和（dp思想） 

	for(int i=1;i<=n-1;i++) cnt[i+1]=cnt[i]+cnt[i+1]; 

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

	{

		while(a[2][i]<a[3][j]&&i<=n) i++;

//		for(int m=1;m<=i-1;m++)

//			ans+=cnt[m] ;

		ans+=cnt[i-1];

	 	

	 } 



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

	return 0;

}

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

#include <cstdio>

#include <algorithm>

using namespace std;



static const int N = 1e5 + 10;

int n;

int a[N], b[N], c[N], cnt1[N], cnt2[N];



int main ()

{

	scanf ("%d", &n);

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

		scanf ("%d", &a[i]);

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

		scanf ("%d", &b[i]);

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

		scanf ("%d", &c[i]);

	sort (a + 1, a + n + 1);

	sort (b + 1, b + n + 1);

	sort (c + 1, c + n + 1);

	int k = 1;

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

	{

		for (; c[k] <= b[i] && k <= n ;)

			++k;

		cnt1[i] = n - k + 1;

	}

	k = 1;

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

	{

		for (; a[k] < b[i] && k <= n ;)

			++k;

		cnt2[i] = k - 1;

	}

	long long ans = 0;

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

		ans += (long long)cnt1[i] * cnt2[i];

	printf ("%lld", ans);

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

#include<cstring>

#include<algorithm>

#include<iostream>

#include<string>

#include<vector>

#include<stack>

#include<bitset>

#include<cstdlib>

#include<cmath>

#include<set>

#include<list>

#include<deque>

#include<map>

#include<queue>

using namespace std;

typedef long long ll;

const double PI = acos(-1.0);

const double eps = 1e-6;

const int INF = 0x3f3f3f3f;



int N =0;

const int MAXN = 1e5+10;

int A[MAXN];

int B[MAXN];

int C[MAXN];



int main(){

	scanf("%d",&N);

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

		scanf("%d",&A[n]);

	}

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

		scanf("%d",&B[n]);

	}

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

		scanf("%d",&C[n]);

	}

	sort(A,A+N);sort(B,B+N);sort(C,C+N);

	long long int ans=0;

	long long int p = 0;

	long long int q = 0;

	

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

		while(A[p]<B[i]&&p<N)	p++;

		while(C[q]<=B[i]&&q<N)	q++;

		ans+=p*(N-q);

	}

	

	printf("%lld",ans);

	

	return 0;

}

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

#include <cstdio>

#include <algorithm>

using namespace std;



static const int N = 1e5 + 10;

int n;

int a[N], b[N], c[N], cnt1[N], cnt2[N];



int main ()

{

	scanf ("%d", &n);

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

		scanf ("%d", &a[i]);

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

		scanf ("%d", &b[i]);

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

		scanf ("%d", &c[i]);

	sort (a + 1, a + n + 1);

	sort (b + 1, b + n + 1);

	sort (c + 1, c + n + 1);

	int k = 1;

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

	{

		for (; c[k] <= b[i] && k <= n ;)

			++k;

		cnt1[i] = n - k + 1;

	}

	k = 1;

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

	{

		for (; a[k] < b[i] && k <= n ;)

			++k;

		cnt2[i] = k - 1;

	}

	long long ans = 0;

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

		ans += (long long)cnt1[i] * cnt2[i];

	printf ("%lld", ans);

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

#include <stdio.h>

#include <string.h>

#include <algorithm>



using namespace std;

const int maxn = 1e6 + 5;

long long a[maxn], b[maxn], c[maxn];



int main()

{

    long long n;

    long long sum = 0;

    scanf("%lld", &n);

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

        scanf("%lld", &a[i]);

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

        scanf("%lld", &b[i]);

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

        scanf("%lld", &c[i]);

    sort(a + 1, a + n + 1);

    sort(b + 1, b + n + 1);

    sort(c + 1, c + n + 1);

    long long l = 0, r = 0;

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

    {

        while(a[l + 1] < b[i] && l + 1 <= n)

            l++;

        while(c[r + 1] <= b[i] && r + 1 <= n )

            r++;

        sum += l * (n - r);

    }

    printf("%lld\n", sum);

    return 0;

}


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

#include <cstdio>

#include <algorithm>

using namespace std;



static const int N = 1e5 + 10;

int n;

int a[N], b[N], c[N], cnt1[N], cnt2[N];



int main ()

{

	scanf ("%d", &n);

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

		scanf ("%d", &a[i]);

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

		scanf ("%d", &b[i]);

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

		scanf ("%d", &c[i]);

	sort (a + 1, a + n + 1);

	sort (b + 1, b + n + 1);

	sort (c + 1, c + n + 1);

	int k = 1;

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

	{

		for (; c[k] <= b[i] && k <= n ;)

			++k;

		cnt1[i] = n - k + 1;

	}

	k = 1;

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

	{

		for (; a[k] < b[i] && k <= n ;)

			++k;

		cnt2[i] = k - 1;

	}

	long long ans = 0;

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

		ans += (long long)cnt1[i] * cnt2[i];

	printf ("%lld", ans);

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



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

#define for1(i, n) for (int i = 1; i <= int(n); ++i)

#define F first

#define S second

#define all(x) (x).begin(),(x).end()

#define sz(x) int(x.size())

#define pb push_back



using namespace std;

using ll=long long;

using pii= pair<int, int>;

mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());

template<typename... T> void rd(T&... args) {((cin>>args), ...);}

template<typename... T> void wr(T... args) {((cout<<args<<" "), ...);cout<<endl;}



int n;

ll k;

const int mod=1e9+7;

struct MAT{

    ll a[55][55];

};

MAT mul(MAT &a,MAT &b){

    MAT c;

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

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

            c.a[i][j]=0;

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

        }

    }

    return c;

}

int main(){

    cin>>n>>k;

    MAT x,ans;

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

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

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

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

    }

    while(k){

        if(k&1)ans=mul(x,ans);

        k>>=1,x=mul(x,x);

    }

    ll out=0;

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

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

    }

    cout<<out%mod<<endl;

	//system("pause");

	return 0;

}


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

using namespace std;

typedef long long ll;

int n;

vector<vector<ll> >vec;

ll k,ans;

const ll M=1e9+7;

vector<vector<ll> >dp,tmp1,tmp2;

void go()

{

    tmp1=dp;

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

	{

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

		{

            dp[i][j]=0;

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

                dp[i][j]=(dp[i][j]+(tmp1[i][k]*tmp1[k][j]))%M;

        }

    }

}

void odd()

{

    tmp1=dp;

    tmp2=vec;

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

	{

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

		{

            dp[i][j]=0;

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

                dp[i][j]=(dp[i][j]+(tmp1[i][k]*tmp2[k][j]))%M;

        }

    }

}

void solve(ll k)

{

    if(k==1)return;

    solve(k/2);

    go();

    if(k%2)odd();

    return;

}

int main()

{

    cin>>n>>k;

    vec.resize(n);

    dp.resize(n);

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

	{

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

		{

            int x;

            cin>>x;

            vec[i].push_back(x);

            dp[i].push_back(x);

        }

    }

    solve(k);

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

        ans+=(dp[i][j]%M);

    cout<<ans%M<<endl;

    return 0;

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



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

#define for1(i, n) for (int i = 1; i <= int(n); ++i)

#define F first

#define S second

#define all(x) (x).begin(),(x).end()

#define sz(x) int(x.size())

#define pb push_back



using namespace std;

using ll=long long;

using pii= pair<int, int>;

mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());

template<typename... T> void rd(T&... args) {((cin>>args), ...);}

template<typename... T> void wr(T... args) {((cout<<args<<" "), ...);cout<<endl;}



int n;

ll k;

const int mod=1e9+7;

struct MAT{

    ll a[55][55];

};

MAT mul(MAT &a,MAT &b){

    MAT c;

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

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

            c.a[i][j]=0;

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

        }

    }

    return c;

}

int main(){

    cin>>n>>k;

    MAT x,ans;

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

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

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

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

    }

    while(k){

        if(k&1)ans=mul(x,ans);

        k>>=1,x=mul(x,x);

    }

    ll out=0;

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

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

    }

    cout<<out%mod<<endl;

	//system("pause");

	return 0;

}


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

#define f first

#define s second

#define pb push_back

#define ENDL '\n'

#define all(a) begin(a),end(a)

#define sz(a) (int)(a.size())

#define deb(a) cout << #a << ": " << a << ENDL

#define fore(i, a, b) for(int i(a), ThkMk(b); i < ThkMk; ++i)

#define _ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);



using namespace std;



typedef long long lli;

typedef long double ld;

typedef pair<lli, lli> ii;

typedef vector<lli> vi;





lli MOD = 1e9 + 7;



vector<vector<lli>> ones(int n) {

	vector<vector<lli>> identity(n, vector<lli>(n));

	fore(i, 0, n) identity[i][i] = 1;

	return identity;

}

vector<vector<lli>> operator*(vector<vector<lli>> &u, vector<vector<lli>> &v) {

    int n = sz(u);

	vector<vector<lli>> ans(n, vector<lli>(n));

	fore(i, 0 ,n) fore(j, 0, n) fore(k, 0, n)

        ans[i][j] = (ans[i][j] + (u[i][k] * v[k][j])) % MOD;

	return ans;

}

vector<vector<lli>> pot(vector<vector<lli>> mat, lli exp) {

	vector<vector<lli>> res = ones(sz(mat));

	while(exp) {

        if(exp % 2) res = res * mat;

        mat = mat * mat;

        exp /= 2;

	}

	return res;

}



int main()

{   _

    lli n, k; cin >> n >> k;

    vector<vector<lli>> m(n, vector<lli>(n));

    fore(i, 0, n) fore(j, 0, n) cin >> m[i][j];

    vector<vector<lli>> res = pot(m, k);

    lli ans = 0;

    for(auto itt : res) for(auto it : itt) ans = (ans + it) % MOD;

    cout << ans << ENDL;

    return 0;

}
// Slower C++ solution:
//#include <boost/multiprecision/cpp_dec_float.hpp>

//#include <boost/multiprecision/cpp_int.hpp>

#include <stdio.h>

#include <iostream>

#include <vector>

#include <string>

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <math.h>

#include <algorithm>

#include <bitset>

#include <iomanip>

using namespace std;

//namespace mp = boost::multiprecision;

//using llll = mp::cpp_int;

// 仮数部が1024ビットの浮動小数点数型(TLEしたら小さくする)

//using Real = mp::number<mp::cpp_dec_float<1024>>;

using ll = long long;

const double EPS = 1e-10;

const ll MOD = 7+(1e+9);





ll N , M;



struct Matrix{

  static const int maxn = 105;

  ll A[maxn][maxn];

  int n;



  Matrix(int n_): n(n_) {

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

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

        A[i][j] = 0;

  }



  Matrix operator * (const Matrix& o) const {

    Matrix ret(n);

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

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

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

          ll c = A[i][k] * o.A[k][j] % MOD;

          ret.A[i][j] = (ret.A[i][j] + c) % MOD;

        }

    return ret;

  }



  static Matrix identity(int n){

    Matrix ret(n);

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

      ret.A[i][i] = 1;

    return ret;

  }



  Matrix operator ^ (long long k) const {

    Matrix ret = identity(n);

    Matrix a = *this;

    while(k){

      if(k & 1)ret = ret * a;

      a = a * a;

      k /= 2;

    }

    return ret;

  }



};



int main(){

  ll n,k;

  cin>>n>>k;

  M=n;

  N=k;

  Matrix a(M);

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

    for(ll j=0;j<M;j++){

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

    }

  }

  a = a ^ (N);

  ll ret = 0;

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

    for(ll j=0;j<M;j++){

      ret=(ret+a.A[i][j])%MOD;

    }

  }

  cout << ret << endl;

}


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

#define mod 1000000007



using namespace std;

long long n,k,total;

struct matrice

{

    vector < vector<long long>> t;

    matrice()

    {

        t.resize(n, vector<long long>(n));

    }



    matrice operator* (const matrice &b)

    {

        matrice ans = matrice();

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

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

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

                {

                    ans.t[i][k] += (t[i][j]*b.t[j][k])%mod;

                    ans.t[i][k] %= mod;

                }

        return ans;

    }

};

int main()

{

    cin>>n>>k;

    vector<vector<long long>> can(n, vector<long long>(n));

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

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

            cin>>can[i][j];



    matrice ans = matrice();

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

        ans.t[i][i]=1;



    matrice m = matrice();

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

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

            m.t[i][j]=can[i][j];



    while(k)

    {

        if(k%2)

        {

            ans=ans * m;

        }

        m = m*m;

        k/=2;

    }



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

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

        {

            total += ans.t[i][j];

            total %= mod;

        }



    cout<<total;

    return 0;

}
// Slower C++ solution:
//#include <boost/multiprecision/cpp_dec_float.hpp>

//#include <boost/multiprecision/cpp_int.hpp>

#include <stdio.h>

#include <iostream>

#include <vector>

#include <string>

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <math.h>

#include <algorithm>

#include <bitset>

#include <iomanip>

using namespace std;

//namespace mp = boost::multiprecision;

//using llll = mp::cpp_int;

// 仮数部が1024ビットの浮動小数点数型(TLEしたら小さくする)

//using Real = mp::number<mp::cpp_dec_float<1024>>;

using ll = long long;

const double EPS = 1e-10;

const ll MOD = 7+(1e+9);





ll N , M;



struct Matrix{

  static const int maxn = 105;

  ll A[maxn][maxn];

  int n;



  Matrix(int n_): n(n_) {

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

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

        A[i][j] = 0;

  }



  Matrix operator * (const Matrix& o) const {

    Matrix ret(n);

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

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

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

          ll c = A[i][k] * o.A[k][j] % MOD;

          ret.A[i][j] = (ret.A[i][j] + c) % MOD;

        }

    return ret;

  }



  static Matrix identity(int n){

    Matrix ret(n);

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

      ret.A[i][i] = 1;

    return ret;

  }



  Matrix operator ^ (long long k) const {

    Matrix ret = identity(n);

    Matrix a = *this;

    while(k){

      if(k & 1)ret = ret * a;

      a = a * a;

      k /= 2;

    }

    return ret;

  }



};



int main(){

  ll n,k;

  cin>>n>>k;

  M=n;

  N=k;

  Matrix a(M);

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

    for(ll j=0;j<M;j++){

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

    }

  }

  a = a ^ (N);

  ll ret = 0;

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

    for(ll j=0;j<M;j++){

      ret=(ret+a.A[i][j])%MOD;

    }

  }

  cout << ret << endl;

}


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

#include <iostream>



using namespace std;



typedef long long ll;

const int MAXN = 51;

const int MOD = 1e9+7;



int n;

ll k;



struct matrix{

	int a[MAXN][MAXN];

	matrix(){

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

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

				a[i][j] = 0;

	}

	matrix(int TP = 0){

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

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

				a[i][j] = 0;

		if(TP)

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

				a[i][i] = 1;

	}

	matrix operator*(const matrix &y)

	{

		matrix res(0);

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

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

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

					res.a[i][j] = (res.a[i][j] + 1ll * a[i][k] * y.a[k][j] % MOD) % MOD;

		return res;

	}

};



inline matrix pw(matrix x, ll p)

{

	matrix res(1);

	for(;p;p>>=1,x=x*x)

		if(p&1) res=res*x;

	return res;

}



matrix x(0);



int main()

{

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

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

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

			scanf("%d",&x.a[i][j]);

	matrix z = pw(x, k);

	int ans = 0;

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

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

			ans = (ans + z.a[i][j]) % MOD;

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

	return 0;

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

#define mn(a, b) (a < b ? a : b)

#define mx(a, b) (a > b ? a : b)

#define f first

#define s second

#define all(v) (v).begin(), (v).end()

#define base 331

#define db(a) cout<<(a)<<"\n";



using namespace std;



typedef long long ll;

typedef unsigned long long ull;



const ll MOD = 1e9 + 7;



struct mat{

    ll matriz[52][52];

    mat(){

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

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

                matriz[i][j] = 0;

        }

    }

    friend mat operator *(const mat &a, const mat &b){

        mat c;

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

            fill(c.matriz[i] + 1, c.matriz[i] + 51, 0);

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

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

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

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

            }

        }

        return c;

    }

};



mat ident(){

    mat c;

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

        c.matriz[i][i] = 1;

    return c;

}



mat qp(ll e, mat b){

    mat a = b, aux = ident();

    if(e == 1)

        return a;

    while(e > 1){

        if(e % 2)

            aux = aux * a;

        a = a * a;

        e /= 2;

    }

    return a * aux;

}





int main(){



    //freopen(".in","r",stdin);

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);

    int n;

    cin>>n;

    ll k;

    cin>>k;

    mat xz;

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

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

            cin>>xz.matriz[i][j];

        }

    }

    mat x = qp(k, xz);

    ll sum = 0;

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

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

            sum = (sum + x.matriz[i][j]) % MOD;

        }

    }

    cout<<sum;

    return 0;

}


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

#include <iostream>



using namespace std;



typedef long long ll;

const int MAXN = 51;

const int MOD = 1e9+7;



int n;

ll k;



struct matrix{

	int a[MAXN][MAXN];

	matrix(){

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

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

				a[i][j] = 0;

	}

	matrix(int TP = 0){

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

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

				a[i][j] = 0;

		if(TP)

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

				a[i][i] = 1;

	}

	matrix operator*(const matrix &y)

	{

		matrix res(0);

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

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

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

					res.a[i][j] = (res.a[i][j] + 1ll * a[i][k] * y.a[k][j] % MOD) % MOD;

		return res;

	}

};



inline matrix pw(matrix x, ll p)

{

	matrix res(1);

	for(;p;p>>=1,x=x*x)

		if(p&1) res=res*x;

	return res;

}



matrix x(0);



int main()

{

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

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

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

			scanf("%d",&x.a[i][j]);

	matrix z = pw(x, k);

	int ans = 0;

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

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

			ans = (ans + z.a[i][j]) % MOD;

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

	return 0;

}