#define PROBLEM "https://judge.yosupo.jp/problem/pow_of_matrix"
//#include"../../template/template.hpp"//#include"../../matrix/matrix.hpp"//#include"../../modint/montgomery-modint.hpp"
#include"../../modulo/binomial.hpp"//usingnamespaceNyaan;usingmint=LazyMontgomeryModInt<998244353>;// using mint = LazyMontgomeryModInt<1000000007>;usingvm=vector<mint>;usingvvm=vector<vm>;Binomial<mint>C;usingnamespaceNyaan;voidq(){inl(N,K);Matrix<mint>m(N);rep(i,N)rep(j,N)in(m[i][j]);m=m^K;rep(i,N)out(m[i]);}voidNyaan::solve(){intt=1;// in(t);while(t--)q();}
#line 1 "verify/verify-yosupo-math/yosupo-pow-of-matrix.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/pow_of_matrix"
//#line 2 "template/template.hpp"
usingnamespacestd;// intrinstic#include<immintrin.h>#include<algorithm>
#include<array>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cfenv>
#include<cfloat>
#include<chrono>
#include<cinttypes>
#include<climits>
#include<cmath>
#include<complex>
#include<cstdarg>
#include<cstddef>
#include<cstdint>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<deque>
#include<fstream>
#include<functional>
#include<initializer_list>
#include<iomanip>
#include<ios>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<random>
#include<set>
#include<sstream>
#include<stack>
#include<streambuf>
#include<string>
#include<tuple>
#include<type_traits>
#include<typeinfo>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>// utility#line 1 "template/util.hpp"
namespaceNyaan{usingll=longlong;usingi64=longlong;usingu64=unsignedlonglong;usingi128=__int128_t;usingu128=__uint128_t;template<typenameT>usingV=vector<T>;template<typenameT>usingVV=vector<vector<T>>;usingvi=vector<int>;usingvl=vector<longlong>;usingvd=V<double>;usingvs=V<string>;usingvvi=vector<vector<int>>;usingvvl=vector<vector<longlong>>;template<typenameT>usingminpq=priority_queue<T,vector<T>,greater<T>>;template<typenameT,typenameU>structP:pair<T,U>{template<typename...Args>P(Args...args):pair<T,U>(args...){}usingpair<T,U>::first;usingpair<T,U>::second;P&operator+=(constP&r){first+=r.first;second+=r.second;return*this;}P&operator-=(constP&r){first-=r.first;second-=r.second;return*this;}P&operator*=(constP&r){first*=r.first;second*=r.second;return*this;}template<typenameS>P&operator*=(constS&r){first*=r,second*=r;return*this;}Poperator+(constP&r)const{returnP(*this)+=r;}Poperator-(constP&r)const{returnP(*this)-=r;}Poperator*(constP&r)const{returnP(*this)*=r;}template<typenameS>Poperator*(constS&r)const{returnP(*this)*=r;}Poperator-()const{returnP{-first,-second};}};usingpl=P<ll,ll>;usingpi=P<int,int>;usingvp=V<pl>;constexprintinf=1001001001;constexprlonglonginfLL=4004004004004004004LL;template<typenameT>intsz(constT&t){returnt.size();}template<typenameT,typenameU>inlineboolamin(T&x,Uy){return(y<x)?(x=y,true):false;}template<typenameT,typenameU>inlineboolamax(T&x,Uy){return(x<y)?(x=y,true):false;}template<typenameT>inlineTMax(constvector<T>&v){return*max_element(begin(v),end(v));}template<typenameT>inlineTMin(constvector<T>&v){return*min_element(begin(v),end(v));}template<typenameT>inlinelonglongSum(constvector<T>&v){returnaccumulate(begin(v),end(v),0LL);}template<typenameT>intlb(constvector<T>&v,constT&a){returnlower_bound(begin(v),end(v),a)-begin(v);}template<typenameT>intub(constvector<T>&v,constT&a){returnupper_bound(begin(v),end(v),a)-begin(v);}constexprlonglongTEN(intn){longlongret=1,x=10;for(;n;x*=x,n>>=1)ret*=(n&1?x:1);returnret;}template<typenameT,typenameU>pair<T,U>mkp(constT&t,constU&u){returnmake_pair(t,u);}template<typenameT>vector<T>mkrui(constvector<T>&v,boolrev=false){vector<T>ret(v.size()+1);if(rev){for(inti=int(v.size())-1;i>=0;i--)ret[i]=v[i]+ret[i+1];}else{for(inti=0;i<int(v.size());i++)ret[i+1]=ret[i]+v[i];}returnret;};template<typenameT>vector<T>mkuni(constvector<T>&v){vector<T>ret(v);sort(ret.begin(),ret.end());ret.erase(unique(ret.begin(),ret.end()),ret.end());returnret;}template<typenameF>vector<int>mkord(intN,Ff){vector<int>ord(N);iota(begin(ord),end(ord),0);sort(begin(ord),end(ord),f);returnord;}template<typenameT>vector<int>mkinv(vector<T>&v){intmax_val=*max_element(begin(v),end(v));vector<int>inv(max_val+1,-1);for(inti=0;i<(int)v.size();i++)inv[v[i]]=i;returninv;}vector<int>mkiota(intn){vector<int>ret(n);iota(begin(ret),end(ret),0);returnret;}template<typenameT>Tmkrev(constT&v){Tw{v};reverse(begin(w),end(w));returnw;}template<typenameT>boolnxp(T&v){returnnext_permutation(begin(v),end(v));}// 返り値の型は入力の T に依存// i 要素目 : [0, a[i])template<typenameT>vector<vector<T>>product(constvector<T>&a){vector<vector<T>>ret;vector<T>v;autodfs=[&](autorc,inti)->void{if(i==(int)a.size()){ret.push_back(v);return;}for(intj=0;j<a[i];j++)v.push_back(j),rc(rc,i+1),v.pop_back();};dfs(dfs,0);returnret;}// F : function(void(T&)), mod を取る操作// T : 整数型のときはオーバーフローに注意するtemplate<typenameT>TPower(Ta,longlongn,constT&I,constfunction<void(T&)>&f){Tres=I;for(;n;f(a=a*a),n>>=1){if(n&1)f(res=res*a);}returnres;}// T : 整数型のときはオーバーフローに注意するtemplate<typenameT>TPower(Ta,longlongn,constT&I=T{1}){returnPower(a,n,I,function<void(T&)>{[](T&)->void{}});}template<typenameT>TRev(constT&v){Tres=v;reverse(begin(res),end(res));returnres;}template<typenameT>vector<T>Transpose(constvector<T>&v){usingU=typenameT::value_type;if(v.empty())return{};intH=v.size(),W=v[0].size();vectorres(W,T(H,U{}));for(inti=0;i<H;i++){for(intj=0;j<W;j++){res[j][i]=v[i][j];}}returnres;}template<typenameT>vector<T>Rotate(constvector<T>&v,intclockwise=true){usingU=typenameT::value_type;intH=v.size(),W=v[0].size();vectorres(W,T(H,U{}));for(inti=0;i<H;i++){for(intj=0;j<W;j++){if(clockwise){res[W-1-j][i]=v[i][j];}else{res[j][H-1-i]=v[i][j];}}}returnres;}}// namespace Nyaan#line 58 "template/template.hpp"
// bit operation#line 1 "template/bitop.hpp"
namespaceNyaan{__attribute__((target("popcnt")))inlineintpopcnt(constu64&a){return__builtin_popcountll(a);}inlineintlsb(constu64&a){returna?__builtin_ctzll(a):64;}inlineintctz(constu64&a){returna?__builtin_ctzll(a):64;}inlineintmsb(constu64&a){returna?63-__builtin_clzll(a):-1;}template<typenameT>inlineintgbit(constT&a,inti){return(a>>i)&1;}template<typenameT>inlinevoidsbit(T&a,inti,boolb){if(gbit(a,i)!=b)a^=T(1)<<i;}constexprlonglongPW(intn){return1LL<<n;}constexprlonglongMSK(intn){return(1LL<<n)-1;}}// namespace Nyaan#line 61 "template/template.hpp"
// inout#line 1 "template/inout.hpp"
namespaceNyaan{template<typenameT,typenameU>ostream&operator<<(ostream&os,constpair<T,U>&p){os<<p.first<<" "<<p.second;returnos;}template<typenameT,typenameU>istream&operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;returnis;}template<typenameT>ostream&operator<<(ostream&os,constvector<T>&v){ints=(int)v.size();for(inti=0;i<s;i++)os<<(i?" ":"")<<v[i];returnos;}template<typenameT>istream&operator>>(istream&is,vector<T>&v){for(auto&x:v)is>>x;returnis;}istream&operator>>(istream&is,__int128_t&x){stringS;is>>S;x=0;intflag=0;for(auto&c:S){if(c=='-'){flag=true;continue;}x*=10;x+=c-'0';}if(flag)x=-x;returnis;}istream&operator>>(istream&is,__uint128_t&x){stringS;is>>S;x=0;for(auto&c:S){x*=10;x+=c-'0';}returnis;}ostream&operator<<(ostream&os,__int128_tx){if(x==0)returnos<<0;if(x<0)os<<'-',x=-x;stringS;while(x)S.push_back('0'+x%10),x/=10;reverse(begin(S),end(S));returnos<<S;}ostream&operator<<(ostream&os,__uint128_tx){if(x==0)returnos<<0;stringS;while(x)S.push_back('0'+x%10),x/=10;reverse(begin(S),end(S));returnos<<S;}voidin(){}template<typenameT,class...U>voidin(T&t,U&...u){cin>>t;in(u...);}voidout(){cout<<"\n";}template<typenameT,class...U,charsep=' '>voidout(constT&t,constU&...u){cout<<t;if(sizeof...(u))cout<<sep;out(u...);}structIoSetupNya{IoSetupNya(){cin.tie(nullptr);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);cerr<<fixed<<setprecision(7);}}iosetupnya;}// namespace Nyaan#line 64 "template/template.hpp"
// debug#line 1 "template/debug.hpp"
namespaceDebugImpl{template<typenameU,typename=void>structis_specialize:false_type{};template<typenameU>structis_specialize<U,typenameconditional<false,typenameU::iterator,void>::type>:true_type{};template<typenameU>structis_specialize<U,typenameconditional<false,decltype(U::first),void>::type>:true_type{};template<typenameU>structis_specialize<U,enable_if_t<is_integral<U>::value,void>>:true_type{};voiddump(constchar&t){cerr<<t;}voiddump(conststring&t){cerr<<t;}voiddump(constbool&t){cerr<<(t?"true":"false");}voiddump(__int128_tt){if(t==0)cerr<<0;if(t<0)cerr<<'-',t=-t;stringS;while(t)S.push_back('0'+t%10),t/=10;reverse(begin(S),end(S));cerr<<S;}voiddump(__uint128_tt){if(t==0)cerr<<0;stringS;while(t)S.push_back('0'+t%10),t/=10;reverse(begin(S),end(S));cerr<<S;}template<typenameU,enable_if_t<!is_specialize<U>::value,nullptr_t>=nullptr>voiddump(constU&t){cerr<<t;}template<typenameT>voiddump(constT&t,enable_if_t<is_integral<T>::value>*=nullptr){stringres;if(t==Nyaan::inf)res="inf";ifconstexpr(is_signed<T>::value){if(t==-Nyaan::inf)res="-inf";}ifconstexpr(sizeof(T)==8){if(t==Nyaan::infLL)res="inf";ifconstexpr(is_signed<T>::value){if(t==-Nyaan::infLL)res="-inf";}}if(res.empty())res=to_string(t);cerr<<res;}template<typenameT,typenameU>voiddump(constpair<T,U>&);template<typenameT>voiddump(constpair<T*,int>&);template<typenameT>voiddump(constT&t,enable_if_t<!is_void<typenameT::iterator>::value>*=nullptr){cerr<<"[ ";for(autoit=t.begin();it!=t.end();){dump(*it);cerr<<(++it==t.end()?"":", ");}cerr<<" ]";}template<typenameT,typenameU>voiddump(constpair<T,U>&t){cerr<<"( ";dump(t.first);cerr<<", ";dump(t.second);cerr<<" )";}template<typenameT>voiddump(constpair<T*,int>&t){cerr<<"[ ";for(inti=0;i<t.second;i++){dump(t.first[i]);cerr<<(i==t.second-1?"":", ");}cerr<<" ]";}voidtrace(){cerr<<endl;}template<typenameHead,typename...Tail>voidtrace(Head&&head,Tail&&...tail){cerr<<" ";dump(head);if(sizeof...(tail)!=0)cerr<<",";trace(std::forward<Tail>(tail)...);}}// namespace DebugImpl#ifdef NyaanDebug
#define trc(...) \
do { \
cerr << "## " << #__VA_ARGS__ << " = "; \
DebugImpl::trace(__VA_ARGS__); \
} while (0)
#else
#define trc(...) (void(0))
#endif
#ifdef NyaanLocal
#define trc2(...) \
do { \
cerr << "## " << #__VA_ARGS__ << " = "; \
DebugImpl::trace(__VA_ARGS__); \
} while (0)
#else
#define trc2(...) (void(0))
#endif
#line 67 "template/template.hpp"
// macro#line 1 "template/macro.hpp"
#define each(x, v) for (auto&& x : v)
#define each2(x, y, v) for (auto&& [x, y] : v)
#define all(v) (v).begin(), (v).end()
#define rep(i, N) for (long long i = 0; i < (long long)(N); i++)
#define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--)
#define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++)
#define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--)
#define reg(i, a, b) for (long long i = (a); i < (b); i++)
#define regr(i, a, b) for (long long i = (b)-1; i >= (a); i--)
#define fi first
#define se second
#define ini(...) \
int __VA_ARGS__; \
in(__VA_ARGS__)
#define inl(...) \
long long __VA_ARGS__; \
in(__VA_ARGS__)
#define ins(...) \
string __VA_ARGS__; \
in(__VA_ARGS__)
#define in2(s, t) \
for (int i = 0; i < (int)s.size(); i++) { \
in(s[i], t[i]); \
}
#define in3(s, t, u) \
for (int i = 0; i < (int)s.size(); i++) { \
in(s[i], t[i], u[i]); \
}
#define in4(s, t, u, v) \
for (int i = 0; i < (int)s.size(); i++) { \
in(s[i], t[i], u[i], v[i]); \
}
#define die(...) \
do { \
Nyaan::out(__VA_ARGS__); \
return; \
} while (0)
#line 70 "template/template.hpp"
namespaceNyaan{voidsolve();}intmain(){Nyaan::solve();}#line 4 "verify/verify-yosupo-math/yosupo-pow-of-matrix.test.cpp"
//#line 2 "matrix/matrix.hpp"
#line 2 "matrix/inverse-matrix.hpp"
#line 2 "matrix/gauss-elimination.hpp"
#line 5 "matrix/gauss-elimination.hpp"
usingnamespacestd;// {rank, det(非正方行列の場合は未定義)} を返す// 型が double や Rational でも動くはず?(未検証)//// pivot 候補 : [0, pivot_end)template<typenameT>std::pair<int,T>GaussElimination(vector<vector<T>>&a,intpivot_end=-1,booldiagonalize=false){if(a.empty())return{0,1};intH=a.size(),W=a[0].size(),rank=0;if(pivot_end==-1)pivot_end=W;Tdet=1;for(intj=0;j<pivot_end;j++){intidx=-1;for(inti=rank;i<H;i++){if(a[i][j]!=T(0)){idx=i;break;}}if(idx==-1){det=0;continue;}if(rank!=idx)det=-det,swap(a[rank],a[idx]);det*=a[rank][j];if(diagonalize&&a[rank][j]!=T(1)){Tcoeff=T(1)/a[rank][j];for(intk=j;k<W;k++)a[rank][k]*=coeff;}intis=diagonalize?0:rank+1;for(inti=is;i<H;i++){if(i==rank)continue;if(a[i][j]!=T(0)){Tcoeff=a[i][j]/a[rank][j];for(intk=j;k<W;k++)a[i][k]-=a[rank][k]*coeff;}}rank++;}returnmake_pair(rank,det);}#line 4 "matrix/inverse-matrix.hpp"
template<typenamemint>vector<vector<mint>>inverse_matrix(constvector<vector<mint>>&a){intN=a.size();assert(N>0);assert(N==(int)a[0].size());vector<vector<mint>>m(N,vector<mint>(2*N));for(inti=0;i<N;i++){copy(begin(a[i]),end(a[i]),begin(m[i]));m[i][N+i]=1;}auto[rank,det]=GaussElimination(m,N,true);if(rank!=N)return{};vector<vector<mint>>b(N);for(inti=0;i<N;i++){copy(begin(m[i])+N,end(m[i]),back_inserter(b[i]));}returnb;}#line 4 "matrix/matrix.hpp"
template<classT>structMatrix{vector<vector<T>>A;Matrix()=default;Matrix(intn,intm):A(n,vector<T>(m,T())){}Matrix(intn):A(n,vector<T>(n,T())){};intH()const{returnA.size();}intW()const{returnA[0].size();}intsize()const{returnA.size();}inlineconstvector<T>&operator[](intk)const{returnA[k];}inlinevector<T>&operator[](intk){returnA[k];}staticMatrixI(intn){Matrixmat(n);for(inti=0;i<n;i++)mat[i][i]=1;return(mat);}Matrix&operator+=(constMatrix&B){intn=H(),m=W();assert(n==B.H()&&m==B.W());for(inti=0;i<n;i++)for(intj=0;j<m;j++)(*this)[i][j]+=B[i][j];return(*this);}Matrix&operator-=(constMatrix&B){intn=H(),m=W();assert(n==B.H()&&m==B.W());for(inti=0;i<n;i++)for(intj=0;j<m;j++)(*this)[i][j]-=B[i][j];return(*this);}Matrix&operator*=(constMatrix&B){intn=H(),m=B.W(),p=W();assert(p==B.H());vector<vector<T>>C(n,vector<T>(m,T{}));for(inti=0;i<n;i++)for(intk=0;k<p;k++)for(intj=0;j<m;j++)C[i][j]+=(*this)[i][k]*B[k][j];A.swap(C);return(*this);}Matrix&operator^=(longlongk){MatrixB=Matrix::I(H());while(k>0){if(k&1)B*=*this;*this*=*this;k>>=1LL;}A.swap(B.A);return(*this);}Matrixoperator+(constMatrix&B)const{return(Matrix(*this)+=B);}Matrixoperator-(constMatrix&B)const{return(Matrix(*this)-=B);}Matrixoperator*(constMatrix&B)const{return(Matrix(*this)*=B);}Matrixoperator^(constlonglongk)const{return(Matrix(*this)^=k);}booloperator==(constMatrix&B)const{assert(H()==B.H()&&W()==B.W());for(inti=0;i<H();i++)for(intj=0;j<W();j++)if(A[i][j]!=B[i][j])returnfalse;returntrue;}booloperator!=(constMatrix&B)const{assert(H()==B.H()&&W()==B.W());for(inti=0;i<H();i++)for(intj=0;j<W();j++)if(A[i][j]!=B[i][j])returntrue;returnfalse;}Matrixinverse()const{assert(H()==W());MatrixB(H());B.A=inverse_matrix(A);returnB;}friendostream&operator<<(ostream&os,constMatrix&p){intn=p.H(),m=p.W();for(inti=0;i<n;i++){os<<(i?" ":"")<<"[";for(intj=0;j<m;j++){os<<p[i][j]<<(j+1==m?"]\n":",");}}return(os);}Tdeterminant()const{MatrixB(*this);assert(H()==W());Tret=1;for(inti=0;i<H();i++){intidx=-1;for(intj=i;j<W();j++){if(B[j][i]!=0){idx=j;break;}}if(idx==-1)return0;if(i!=idx){ret*=T(-1);swap(B[i],B[idx]);}ret*=B[i][i];Tinv=T(1)/B[i][i];for(intj=0;j<W();j++){B[i][j]*=inv;}for(intj=i+1;j<H();j++){Ta=B[j][i];if(a==0)continue;for(intk=i;k<W();k++){B[j][k]-=B[i][k]*a;}}}returnret;}};/**
* @brief 行列ライブラリ
*/#line 6 "verify/verify-yosupo-math/yosupo-pow-of-matrix.test.cpp"
//#line 2 "modint/montgomery-modint.hpp"
template<uint32_tmod>structLazyMontgomeryModInt{usingmint=LazyMontgomeryModInt;usingi32=int32_t;usingu32=uint32_t;usingu64=uint64_t;staticconstexpru32get_r(){u32ret=mod;for(i32i=0;i<4;++i)ret*=2-mod*ret;returnret;}staticconstexpru32r=get_r();staticconstexpru32n2=-u64(mod)%mod;static_assert(mod<(1<<30),"invalid, mod >= 2 ^ 30");static_assert((mod&1)==1,"invalid, mod % 2 == 0");static_assert(r*mod==1,"this code has bugs.");u32a;constexprLazyMontgomeryModInt():a(0){}constexprLazyMontgomeryModInt(constint64_t&b):a(reduce(u64(b%mod+mod)*n2)){};staticconstexpru32reduce(constu64&b){return(b+u64(u32(b)*u32(-r))*mod)>>32;}constexprmint&operator+=(constmint&b){if(i32(a+=b.a-2*mod)<0)a+=2*mod;return*this;}constexprmint&operator-=(constmint&b){if(i32(a-=b.a)<0)a+=2*mod;return*this;}constexprmint&operator*=(constmint&b){a=reduce(u64(a)*b.a);return*this;}constexprmint&operator/=(constmint&b){*this*=b.inverse();return*this;}constexprmintoperator+(constmint&b)const{returnmint(*this)+=b;}constexprmintoperator-(constmint&b)const{returnmint(*this)-=b;}constexprmintoperator*(constmint&b)const{returnmint(*this)*=b;}constexprmintoperator/(constmint&b)const{returnmint(*this)/=b;}constexprbooloperator==(constmint&b)const{return(a>=mod?a-mod:a)==(b.a>=mod?b.a-mod:b.a);}constexprbooloperator!=(constmint&b)const{return(a>=mod?a-mod:a)!=(b.a>=mod?b.a-mod:b.a);}constexprmintoperator-()const{returnmint()-mint(*this);}constexprmintoperator+()const{returnmint(*this);}constexprmintpow(u64n)const{mintret(1),mul(*this);while(n>0){if(n&1)ret*=mul;mul*=mul;n>>=1;}returnret;}constexprmintinverse()const{intx=get(),y=mod,u=1,v=0,t=0,tmp=0;while(y>0){t=x/y;x-=t*y,u-=t*v;tmp=x,x=y,y=tmp;tmp=u,u=v,v=tmp;}returnmint{u};}friendostream&operator<<(ostream&os,constmint&b){returnos<<b.get();}friendistream&operator>>(istream&is,mint&b){int64_tt;is>>t;b=LazyMontgomeryModInt<mod>(t);return(is);}constexpru32get()const{u32ret=reduce(a);returnret>=mod?ret-mod:ret;}staticconstexpru32get_mod(){returnmod;}};#line 2 "modulo/binomial.hpp"
#line 6 "modulo/binomial.hpp"
usingnamespacestd;// コンストラクタの MAX に 「C(n, r) や fac(n) でクエリを投げる最大の n 」// を入れると倍速くらいになる// mod を超えて前計算して 0 割りを踏むバグは対策済みtemplate<typenameT>structBinomial{vector<T>f,g,h;Binomial(intMAX=0){assert(T::get_mod()!=0&&"Binomial<mint>()");f.resize(1,T{1});g.resize(1,T{1});h.resize(1,T{1});if(MAX>0)extend(MAX+1);}voidextend(intm=-1){intn=f.size();if(m==-1)m=n*2;m=min<int>(m,T::get_mod());if(n>=m)return;f.resize(m);g.resize(m);h.resize(m);for(inti=n;i<m;i++)f[i]=f[i-1]*T(i);g[m-1]=f[m-1].inverse();h[m-1]=g[m-1]*f[m-2];for(inti=m-2;i>=n;i--){g[i]=g[i+1]*T(i+1);h[i]=g[i]*f[i-1];}}Tfac(inti){if(i<0)returnT(0);while(i>=(int)f.size())extend();returnf[i];}Tfinv(inti){if(i<0)returnT(0);while(i>=(int)g.size())extend();returng[i];}Tinv(inti){if(i<0)return-inv(-i);while(i>=(int)h.size())extend();returnh[i];}TC(intn,intr){if(n<0||n<r||r<0)returnT(0);returnfac(n)*finv(n-r)*finv(r);}inlineToperator()(intn,intr){returnC(n,r);}template<typenameI>Tmultinomial(constvector<I>&r){static_assert(is_integral<I>::value==true);intn=0;for(auto&x:r){if(x<0)returnT(0);n+=x;}Tres=fac(n);for(auto&x:r)res*=finv(x);returnres;}template<typenameI>Toperator()(constvector<I>&r){returnmultinomial(r);}TC_naive(intn,intr){if(n<0||n<r||r<0)returnT(0);Tret=T(1);r=min(r,n-r);for(inti=1;i<=r;++i)ret*=inv(i)*(n--);returnret;}TP(intn,intr){if(n<0||n<r||r<0)returnT(0);returnfac(n)*finv(n-r);}// [x^r] 1 / (1-x)^nTH(intn,intr){if(n<0||r<0)returnT(0);returnr==0?1:C(n+r-1,r);}};#line 9 "verify/verify-yosupo-math/yosupo-pow-of-matrix.test.cpp"
//usingnamespaceNyaan;usingmint=LazyMontgomeryModInt<998244353>;// using mint = LazyMontgomeryModInt<1000000007>;usingvm=vector<mint>;usingvvm=vector<vm>;Binomial<mint>C;usingnamespaceNyaan;voidq(){inl(N,K);Matrix<mint>m(N);rep(i,N)rep(j,N)in(m[i][j]);m=m^K;rep(i,N)out(m[i]);}voidNyaan::solve(){intt=1;// in(t);while(t--)q();}