#include #include #include using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000005 #define Inf64 1000000000000000001LL vector get(vector a){ int n = a.size(); vector res(n+1,0); res[0] = 1; vector t = {1,-1,2,-2,4,-4,8,-8}; vector dp(8,0); dp[0] = 1; rep(i,n){ vector ndp(8); rep(j,8){ int x = a[i]; x *= t[j]; int nj = -1; rep(k,8){ if (t[k] == x) { nj = k; break; } } if(nj==-1)continue; ndp[nj] += dp[j]; } res[i+1] += ndp[6]; ndp[0] += ndp[6]; dp = ndp; } return res; } mint dp[1000000]; vector x,y; vector a; void dfs(int l,int r){ if(l==r)return; int m = (l+r)/2; dfs(l,m); dfs(m,r); } int main(){ int N,K; cin>>N>>K; a.resize(N); rep(i,N)cin>>a[i]; vector sum(N+1); vector sign(N+1); rep(i,N){ if(abs(a[i])==2)sum[i+1]++; sum[i+1] += sum[i]; if(a[i]<0)sign[i+1] = 1; sign[i+1] ^= sign[i]; } auto x = get(a); reverse(a.begin(),a.end()); auto y = get(a); reverse(a.begin(),a.end()); rep(i,sum.back()+1){ if(i<=2)continue; int d0 = distance(sum.begin(),lower_bound(sum.begin(),sum.end(),i-3)); int d1 = distance(sum.begin(),lower_bound(sum.begin(),sum.end(),i)); vector> xs(2),ys(2); { int c = d0; while(c <= N && sum[c] == i-3){ int t = sign[c]; xs[t].push_back(x[c]); xs[t^1].push_back(0); c++; } } { int c = d1; while(c <= N && sum[c] == i){ int t = sign[c]; ys[t].push_back(y[N-c]); ys[t^1].push_back(0); c++; } } rep(ii,2){ reverse(xs[ii].begin(),xs[ii].end()); auto z = convolution(xs[ii],ys[ii]); rep(j,z.size()){ int jj = j - ((int)xs[ii].size()-1); jj += d1; jj -= d0; if(jj<0)continue; dp[jj] += z[j]; } } } mint ans = 0; rep(i,N+1){ ans += dp[i] * mint(i).pow(K); } cout<