// かなり綺麗な構造ある // 畳み込みでそれぞれの長さの寄与求められる O(N log N) // これ結構テストケース弱そう?です (あとでhackしてみます) // -2 -2 -2 // とか落ちる人は落ちそう /** author: shobonvip created: 2025.08.22 22:53:51 **/ #include using namespace std; //* ATCODER #include using namespace atcoder; typedef modint998244353 mint; //*/ /* BOOST MULTIPRECISION #include using namespace boost::multiprecision; //*/ typedef long long ll; #define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++) #define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--) #define all(v) v.begin(), v.end() template bool chmin(T &a, const T &b) { if (a <= b) return false; a = b; return true; } template bool chmax(T &a, const T &b) { if (a >= b) return false; a = b; return true; } template T max(vector &a){ assert(!a.empty()); T ret = a[0]; for (int i=0; i<(int)a.size(); i++) chmax(ret, a[i]); return ret; } template T min(vector &a){ assert(!a.empty()); T ret = a[0]; for (int i=0; i<(int)a.size(); i++) chmin(ret, a[i]); return ret; } template T sum(vector &a){ T ret = 0; for (int i=0; i<(int)a.size(); i++) ret += a[i]; return ret; } mint op(mint a,mint b){ return a*b; } mint e(){ return 1; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n, k; cin >> n >> k; vector a(n); rep(i,0,n) cin >> a[i]; vector is_good(n+1); is_good[0]=1; vector twos; rep(i,0,n) { if(abs(a[i])==2){ twos.push_back(i); } if(a[i]<0){ if(is_good[i])is_good[i+1]=0; else is_good[i+1]=1; }else{ is_good[i+1]=is_good[i]; } } if(!is_good[n]){ cout<<0<<'\n'; return 0; } if((int)twos.size()==0||(int)twos.size()%3!=0){ cout<<0<<'\n'; return 0; } if((int)twos.size()==3){ ll val=1; rep(i,0,n){ val*=a[i]; } if(val==8){ cout<seg(m); vector tar(m,vector(0)); rep(i,0,m){ rep(j,twos[3*i+2]+1,twos[3*i+3]+1){ if(is_good[j]) tar[i].push_back(1); else tar[i].push_back(0); } if(sum(tar[i])==0){ cout<<0<<'\n'; return 0; } seg.set(i,mint(sum(tar[i]))); } vector kiyo(n+1); { mint keis=seg.prod(1,m); rep(j,0,tar.front().size()){ kiyo[j+twos[2]+1]+=tar.front()[j]*keis; } } { mint keis=seg.prod(0,m-1); reverse(all(tar.back())); rep(j,0,tar.back().size()){ kiyo[j+n-twos[(int)twos.size()-3]]+=tar.back()[j]*keis; } reverse(all(tar.back())); } rep(i,0,m-1){ reverse(all(tar[i])); vector f=convolution(tar[i],tar[i+1]); mint keis=seg.prod(0,i)*seg.prod(i+2,m); rep(j,0,(int)f.size()){ kiyo[j+twos[3*i+5]-twos[3*i+3]+1]+=f[j]*keis; } reverse(all(tar[i])); } mint ans=0; rep(i,1,n+1){ ans+=kiyo[i]*mint(i).pow(k); } cout<