CF1140E.Palindrome-less Arrays

Let's denote that some array $b$ is bad if it contains a subarray $b_l, b_{l+1}, \dots, b_{r}$ of odd length more than $1$ ($l \lt r$ and $r - l + 1$ is odd) such that $\forall i \in {0, 1, \dots, r - l}$ $b_{l + i} = b_{r - i}$.

If an array is not bad, it is good.

Now you are given an array $a_1, a_2, \dots, a_n$. Some elements are replaced by $-1$. Calculate the number of good arrays you can obtain by replacing each $-1$ with some integer from $1$ to $k$.

Since the answer can be large, print it modulo $998244353$.

我们称某个数组 $b$ 是“坏的”，如果它包含一个长度为大于 $1$ 的奇数的子数组 $b_l, b_{l+1}, \dots, b_{r}$（即 $l \lt r$ 且 $r - l + 1$ 为奇数），满足对所有 $i \in \{0, 1, \dots, r - l\}$，均有 $b_{l + i} = b_{r - i}$。

若一个数组不是“坏的”，则称其为“好的”。

现给你一个数组 $a_1, a_2, \dots, a_n$，其中部分元素被替换为 $-1$。你需要计算：将每个 $-1$ 替换为 $1$ 到 $k$ 之间的某个整数后，能构成多少个“好的”数组。

由于答案可能很大，请输出其对 $998244353$ 取模的结果。

The first line contains two integers $n$ and $k$ ($2 \le n, k \le 2 \cdot 10^5$) — the length of array $a$ and the size of "alphabet", i. e., the upper bound on the numbers you may use to replace $-1$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($a_i = -1$ or $1 \le a_i \le k$) — the array $a$.

第一行包含两个整数 $n$ 和 $k$（$2 \le n, k \le 2 \cdot 10^5$）—— 分别表示数组 $a$ 的长度以及“字母表”的大小，即用于替换 $-1$ 的数字的上界。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（每个 $a_i$ 要么为 $-1$，要么满足 $1 \le a_i \le k$）—— 即数组 $a$。

Print one integer — the number of good arrays you can get, modulo $998244353$.

输出一个整数——你能得到的好数组的数量，对 $998244353$ 取模。