A12559. 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 < 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$ .

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$ .

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