Mảng không palindrome

Một mảng $b$ được gọi là xấu nếu nó chứa một dãy con liên tiếp $b_l,b_{l+1},\dots ,b_r$ có độ dài lẻ lớn hơn $1$ (tức là $l<r$ và $r-l+1$ là số lẻ) sao cho với mọi $i\in \{0,1,\dots ,r-l\}$ ta có $b_{l+i}=b_{r-i}$.

Nói cách khác, $b$ là xấu nếu nó chứa một dãy con liên tiếp độ dài lẻ $\ge 3$ là một palindrome. Nếu mảng không xấu thì gọi là tốt.

Cho mảng $a_1,a_2,\dots ,a_n$ trong đó một số phần tử đã bị thay bởi $-1$. Hãy đếm số mảng tốt có thể nhận được bằng cách thay mỗi $-1$ bởi một số nguyên trong đoạn $[1,k]$.

Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho $998244353$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ — mỗi $a_i$ bằng $-1$ hoặc nằm trong đoạn $[1,k]$.

Dữ liệu ra

• In ra một số nguyên duy nhất là số mảng tốt thu được, lấy theo modulo $998244353$.

Ràng buộc

• $2\le n,k\le 2·{10}^5$.
• Mỗi $a_i$ bằng $-1$ hoặc nằm trong $[1,k]$.

Ví dụ