#include #include using namespace std; using namespace atcoder; using ll = long long; using mint = atcoder::modint998244353; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, k, v, sv = 0, f = 0; cin >> n >> k; vector> tb(n / 3 + 1); tb[0].emplace_back(0); for(int i = 0; i < n; i++){ cin >> v; sv += (abs(v) == 2); f ^= (v < 0); if(sv % 3 == 0 && f == 0){ tb[sv / 3].emplace_back(i + 1); } } vector dp(n + 1), dp2(n + 1), len(n + 1); for(int i = 1; i <= n; i++) len[i] = mint::raw(i).pow(k); dp[0] = 1; for(int i = 0; i + 1 < tb.size(); i++){ if(tb[i + 1].empty()) break; int l = tb[i][0], r0 = tb[i].back() + 1; vector tmp{dp.begin() + l, dp.begin() + r0}; vector coef{len.begin(), len.begin() + (tb[i + 1].back() - l + 1)}; mint sv1 = accumulate(dp.begin() + l, dp.begin() + r0, mint(0)); mint sv2 = accumulate(dp2.begin() + l, dp2.begin() + r0, mint(0)); auto add = convolution(tmp, coef); for(auto p : tb[i + 1]){ dp2[p] = add[p - l] + sv2; dp[p] = sv1; } } cout << dp2[n].val() << '\n'; }