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


-----Input-----

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


-----Output-----

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


-----Examples-----
Input
2 3
-1 -1

Output
9

Input
5 2
1 -1 -1 1 2

Output
0

Input
5 3
1 -1 -1 1 2

Output
2

Input
4 200000
-1 -1 12345 -1

Output
735945883

Difficulty: HARD
Tags: Dynamic programming

Combinatorics

Divide and conquer
Skill types: Dynamic programming

Starter code:

Solutions:
import io, os
input = io.StringIO(os.read(0, os.fstat(0).st_size).decode()).readline
MOD = 998244353
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
grps = []
lt = None
for start in (0, 1):
	for i in range(start, n, 2):
		if a[i] == -1:
			if lt is None:
				if i - 2 < 0:
					lt = -1
				else:
					lt = a[i - 2]
				sz = 0
			sz += 1
			if i + 2 >= n:
				grps.append((lt, -1, sz))
				lt = None
			elif a[i + 2] != -1:
				grps.append((lt, a[i + 2], sz))
				lt = None
ans = int(all((a[i] != a[i + 2] for i in range(n - 2) if a[i] != -1)))
for (lt, rt, sz) in grps:
	if sz == 1:
		cur = k if lt == -1 and rt == -1 else k - 1 if lt == -1 or rt == -1 or lt == rt else k - 2
	else:
		(eq, neq) = (1 if lt == -1 else 0, 1)
		for _ in range(sz - 1):
			(eq, neq) = (neq * (k - 1) % MOD, (neq * (k - 2) + eq) % MOD)
		cur = neq * (k - 1) + eq if rt == -1 else neq * (k - 1) if lt == rt else neq * (k - 2) + eq
	ans = ans * cur % MOD
print(ans)


input1 = input('').split(' ')
k = int(input1.pop())
n = int(input1.pop())
input2 = input('').split(' ')
lis11 = []
lis12 = []
lis21 = []
lis22 = []
lisk = []
long = 0
op = 1
for i in range(n):
	if i % 2 == 0:
		lis11.append(int(input2[i]))
	else:
		lis12.append(int(input2[i]))
tong = [0, 1, k - 1]
yi = [0, 1, k - 2]
for i in range((n + 1) // 2):
	if lis11[i] != -1:
		lis21.append(i)
		if len(lis21) > 1:
			if i - lis21[-2] > long:
				long = i - lis21[-2]
	if (i > 0) & (lis11[i] > 0):
		if lis11[i - 1] == lis11[i]:
			lisk.append(0)
for i in range(n // 2):
	if lis12[i] != -1:
		lis22.append(i)
		if len(lis22) > 1:
			if i - lis22[-2] > long:
				long = i - lis22[-2]
	if (i > 0) & (lis12[i] > 0):
		if lis12[i - 1] == lis12[i]:
			lisk.append(0)
for i in range(3, long + 1):
	tong.append(int(yi[i - 1]) * (k - 1) % 998244353)
	yi.append((int(yi[i - 1]) * (k - 2) + tong[i - 1]) % 998244353)
if lis21:
	for i in range(lis21[0] - lis21[-1] + (n + 1) // 2 - 1):
		lisk.append(k - 1)
	for i in range(1, len(lis21)):
		if lis11[lis21[i]] == lis11[lis21[i - 1]]:
			lisk.append(tong[lis21[i] - lis21[i - 1]])
		else:
			lisk.append(yi[lis21[i] - lis21[i - 1]])
else:
	lisk.append(k)
	for i in range(1, (n + 1) // 2):
		lisk.append(k - 1)
if lis22:
	for i in range(lis22[0] - lis22[-1] + n // 2 - 1):
		lisk.append(k - 1)
	for i in range(1, len(lis22)):
		if lis12[lis22[i]] == lis12[lis22[i - 1]]:
			lisk.append(tong[lis22[i] - lis22[i - 1]])
		else:
			lisk.append(yi[lis22[i] - lis22[i - 1]])
else:
	lisk.append(k)
	for i in range(1, n // 2):
		lisk.append(k - 1)
if len(lisk) > 0:
	for i in range(len(lisk)):
		op = op * lisk[i] % 998244353
print(op)


import sys
mod = 998244353

def mult(a, b):
	y = 1
	for i in range(b):
		y = y * a % mod
	return y

def getS(cnt, k, b1, b2):
	if b1 < b2:
		(b1, b2) = (b2, b1)
	if b1 == b2 == 0:
		s = mult(k - 1, cnt - 1)
		s = s * k % mod
		return s
	if b2 == 0:
		return mult(k - 1, cnt)
	re = [k - 1] * cnt
	for i in range(1, cnt):
		re[i] = re[i - 1] * (k - 1) % mod
	re[0] = k - (1 if b1 == b2 else 2)
	tot = 0
	mm = 1
	for i in range(cnt - 1, -1, -1):
		tot += mm * re[i]
		mm *= -1
		tot = (tot + mod) % mod
	return tot

def solve(x, k):
	n = len(x)
	x = [0] + x + [0]
	st = -1
	rt = 1
	for i in range(n + 2):
		if x[i] != -1:
			if st != -1:
				rt = rt * getS(i - st, k, x[st - 1], x[i]) % mod
			st = -1
		elif st == -1:
			st = i
	return rt
(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
for i in range(0, n - 2):
	if a[i] != -1 and a[i] == a[i + 2]:
		print(0)
		return
even = solve(a[::2], k)
odd = solve(a[1::2], k)
print(even * odd % mod)


import sys
input = sys.stdin.readline

def compress(string):
	n = len(string)
	(begin, cnt) = (0, 0)
	ans = []
	if n == 0:
		return ans
	for end in range(n + 1):
		if end == n or string[begin] != string[end]:
			ans.append((string[begin], cnt))
			(begin, cnt) = (end, 1)
		else:
			cnt += 1
	return ans
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
MOD = 998244353
dp = [[0] * 2 for i in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	dp[i + 1][0] += dp[i][1]
	dp[i + 1][0] %= MOD
	dp[i + 1][1] += dp[i][0] * (k - 1)
	dp[i + 1][1] += dp[i][1] * (k - 2)
	dp[i + 1][1] %= MOD
dq = [0 for i in range(n + 1)]
dq[1] = k
for i in range(1, n):
	dq[i + 1] += dq[i] * (k - 1)
	dq[i + 1] %= MOD
odd = []
even = []
for (i, val) in enumerate(a):
	if i % 2 == 0:
		odd.append(val)
	else:
		even.append(val)
ans = 1
odd = compress(odd)
for (i, (val, cnt)) in enumerate(odd):
	if val != -1 and cnt > 1:
		ans = 0
		continue
	if val != -1:
		continue
	else:
		if i == 0:
			tmp = dq[cnt]
			if i + 1 == len(odd):
				ans *= tmp
				ans %= MOD
			else:
				ans *= tmp * pow(k, MOD - 2, MOD) * (k - 1)
				ans %= MOD
			continue
		(tmp1, tmp2) = dp[cnt]
		if cnt == 1:
			if i + 1 == len(odd):
				ans *= tmp2
				ans %= MOD
			elif odd[i + 1][0] == odd[i - 1][0]:
				ans *= tmp2
				ans %= MOD
			elif odd[i + 1][0] != odd[i - 1][0]:
				ans *= tmp2 * pow(k - 1, MOD - 2, MOD) * (k - 2)
				ans %= MOD
		elif i + 1 == len(odd):
			ans *= tmp1 + tmp2
			ans %= MOD
		elif odd[i + 1][0] == odd[i - 1][0]:
			ans *= tmp2
			ans %= MOD
		elif odd[i + 1][0] != odd[i - 1][0]:
			ans *= tmp1 + tmp2 * pow(k - 1, MOD - 2, MOD) * (k - 2)
			ans %= MOD
odd = compress(even)
for (i, (val, cnt)) in enumerate(odd):
	if val != -1 and cnt > 1:
		ans = 0
		continue
	if val != -1:
		continue
	else:
		if i == 0:
			tmp = dq[cnt]
			if i + 1 == len(odd):
				ans *= tmp
				ans %= MOD
			else:
				ans *= tmp * pow(k, MOD - 2, MOD) * (k - 1)
				ans %= MOD
			continue
		(tmp1, tmp2) = dp[cnt]
		if cnt == 1:
			if i + 1 == len(odd):
				ans *= tmp2
				ans %= MOD
			elif odd[i + 1][0] == odd[i - 1][0]:
				ans *= tmp2
				ans %= MOD
			elif odd[i + 1][0] != odd[i - 1][0]:
				ans *= tmp2 * pow(k - 1, MOD - 2, MOD) * (k - 2)
				ans %= MOD
		elif i + 1 == len(odd):
			ans *= tmp1 + tmp2
			ans %= MOD
		elif odd[i + 1][0] == odd[i - 1][0]:
			ans *= tmp2
			ans %= MOD
		elif odd[i + 1][0] != odd[i - 1][0]:
			ans *= tmp1 + tmp2 * pow(k - 1, MOD - 2, MOD) * (k - 2)
			ans %= MOD
print(ans % MOD)


import io, os
input = io.StringIO(os.read(0, os.fstat(0).st_size).decode()).readline
ii = lambda : int(input())
mi = lambda : map(int, input().split())
li = lambda : list(mi())
MOD = 998244353
(n, k) = mi()
a = li()
grps = []
ok = 1
for i in range(1, n - 1):
	if a[i - 1] == a[i + 1] and a[i - 1] != -1:
		ok = 0
		break
lt = sz = None
for i in range(0, n, 2):
	if a[i] == -1:
		if lt is None:
			if i - 2 < 0:
				lt = -1
			else:
				lt = a[i - 2]
			sz = 0
		sz += 1
		if i + 2 >= n:
			grps.append((lt, -1, sz))
			lt = None
		elif a[i + 2] != -1:
			grps.append((lt, a[i + 2], sz))
			lt = None
lt = sz = None
for i in range(1, n, 2):
	if a[i] == -1:
		if lt is None:
			if i - 2 < 0:
				lt = -1
			else:
				lt = a[i - 2]
			sz = 0
		sz += 1
		if i + 2 >= n:
			grps.append((lt, -1, sz))
			lt = None
		elif a[i + 2] != -1:
			grps.append((lt, a[i + 2], sz))
			lt = None
ans = ok
for (lt, rt, sz) in grps:
	(lt, rt) = (min(lt, rt), max(lt, rt))
	if sz == 1:
		if lt == -1:
			if rt == -1:
				cur = k
			else:
				cur = k - 1
		elif lt == rt:
			cur = k - 1
		else:
			cur = k - 2
	else:
		if lt == -1:
			(eq, neq) = (1, 1)
		else:
			(eq, neq) = (0, 1)
		for _ in range(sz - 1):
			eq2 = neq * (k - 1)
			neq2 = neq * (k - 2) + eq
			(eq, neq) = (eq2 % MOD, neq2 % MOD)
		if rt == -1:
			cur = neq * (k - 1) + eq
		elif lt == rt:
			cur = neq * (k - 1)
		else:
			cur = neq * (k - 2) + eq
	ans = ans * cur % MOD
print(ans)


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
(x, y) = (a[0::2], a[1::2])
if any((x[i] != -1 and x[i + 1] != -1 and (x[i] == x[i + 1]) for i in range(len(x) - 1))):
	print(0)
	sys.exit(0)
if any((y[i] != -1 and y[i + 1] != -1 and (y[i] == y[i + 1]) for i in range(len(y) - 1))):
	print(0)
	sys.exit(0)
M = 998244353
dp = [[1 for _ in range(4)] for _ in range(n + 1)]
dp[1][0] = k
dp[1][1] = k - 1
dp[1][2] = k - 1
dp[1][3] = k - 2
for i in range(2, n + 1):
	dp[i][0] = k * dp[i - 1][1] % M
	dp[i][1] = (k - 1) * dp[i - 1][1] % M
	dp[i][2] = (k - 1) * dp[i - 1][3] % M
	dp[i][3] = (dp[i - 1][2] + (k - 2) * dp[i - 1][3]) % M
res = 1
for l in [x, y]:
	if all((el == -1 for el in l)):
		res *= dp[len(l)][0]
		continue
	(left, right) = (0, len(l) - 1)
	(cl, cr) = (0, 0)
	while l[left] == -1:
		cl += 1
		left += 1
	while l[right] == -1:
		cr += 1
		right -= 1
	res *= dp[cl][1] * dp[cr][1]
	res %= M
	stack = [l[left]]
	for i in range(left + 1, right + 1):
		if len(stack) == 1 or stack[-1] == -1:
			stack.append(l[i])
		else:
			res *= dp[max(0, len(stack) - 2)][2 if stack[0] == stack[-1] else 3]
			res %= M
			stack = [stack[-1], l[i]]
	res *= dp[max(0, len(stack) - 2)][2 if stack[0] == stack[-1] else 3]
	res %= M
print(res % M)


import sys
from heapq import heappush, heappop

class Main:

	def __init__(self):
		self.buff = None
		self.index = 0

	def __next__(self):
		if self.buff is None or self.index == len(self.buff):
			self.buff = sys.stdin.readline().split()
			self.index = 0
		val = self.buff[self.index]
		self.index += 1
		return val

	def next_int(self):
		return int(next(self))

	def pp(self, a, b, mod):
		if b == 0:
			return 1
		tmp = self.pp(a, b // 2, mod)
		tmp = tmp * tmp % mod
		if b % 2 == 1:
			tmp = tmp * a % mod
		return tmp

	def same(self, cc, k, mod):
		t = 1
		y = 0
		for i in range(0, cc):
			tt = y
			yy = (t * (k - 1) + y * (k - 2)) % mod
			y = yy
			t = tt
		return y

	def diff(self, cc, k, mod):
		t = 0
		y = 1
		for i in range(0, cc):
			tt = y
			yy = (t * (k - 1) + y * (k - 2)) % mod
			y = yy
			t = tt
		return y

	def solve(self):
		n = self.next_int()
		k = self.next_int()
		mod = 998244353
		pre = [-1, -1]
		cc = [0, 0]
		ans = 1
		for i in range(0, n):
			d = self.next_int()
			ii = i % 2
			if d == -1:
				cc[ii] += 1
			else:
				if pre[ii] == -1:
					ans = ans * self.pp(k - 1, cc[ii], mod) % mod
				elif pre[ii] == d:
					ans = ans * self.same(cc[ii], k, mod) % mod
				else:
					ans = ans * self.diff(cc[ii], k, mod) % mod
				cc[ii] = 0
				pre[ii] = d
		if cc[0] == (n + 1) // 2:
			ans = ans * k * self.pp(k - 1, cc[0] - 1, mod) % mod
		else:
			ans = ans * self.pp(k - 1, cc[0], mod) % mod
		if cc[1] == n // 2:
			ans = ans * k * self.pp(k - 1, cc[1] - 1, mod) % mod
		else:
			ans = ans * self.pp(k - 1, cc[1], mod) % mod
		print(ans)

def __starting_point():
	Main().solve()
__starting_point()


import sys
mod = 998244353
(n, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
ub = [0 for i in range(n)]
b = [[0, 0] for i in range(n)]
ub[0] = 1
b[0] = [0, 1]
for i in range(1, n):
	ub[i] = ub[i - 1] * (k - 1) % mod
	sb = b[i - 1][0] + b[i - 1][1] * (k - 1) % mod
	if sb >= mod:
		sb -= mod
	for j in range(2):
		b[i][j] = sb - b[i - 1][j]
		if b[i][j] < 0:
			b[i][j] += mod
ans = 1
for arr in [a[::2], a[1::2]]:
	for i in range(1, len(arr)):
		if arr[i] != -1 and arr[i] == arr[i - 1]:
			print(0)
			sys.exit()
	cur = -1
	for (i, x) in enumerate(arr):
		if x == -1:
			continue
		cnt = i - cur - 1
		if cnt > 0:
			if cur == -1:
				ans = ans * ub[cnt - 1] * (k - 1) % mod
			else:
				s = b[cnt - 1][0] + b[cnt - 1][1] * (k - 1) % mod
				if s >= mod:
					s -= mod
				if x == arr[cur]:
					s -= b[cnt - 1][0]
				else:
					s -= b[cnt - 1][1]
				if s < 0:
					s += mod
				ans = ans * s % mod
		cur = i
	if cur == -1:
		ans = ans * ub[len(arr) - 1] * k % mod
	elif cur < len(arr) - 1:
		cnt = len(arr) - cur - 1
		s = b[cnt - 1][0] + b[cnt - 1][1] * (k - 1) % mod
		if s >= mod:
			s -= mod
		ans = ans * s % mod
print(ans)


import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def main():
	from itertools import groupby
	(n, k) = map(int, input().split())
	a = (-2, -2) + tuple(map(int, input().split())) + (-2, -2)
	if any((a[i] != -1 and a[i] == a[j] for (i, j) in zip(range(0, n + 4, 2), range(2, n + 4, 2)))) or any((a[i] != -1 and a[i] == a[j] for (i, j) in zip(range(1, n + 4, 2), range(3, n + 4, 2)))):
		print(0)
		exit()
	m = (n + 1 >> 1) + 10
	mod = 998244353
	dp = [array('i', [0]) * m for _ in range(4)]
	(dp[0][1], dp[1][1], dp[2][1], dp[3][1]) = (k - 1, k - 2, k - 1, k)
	for i in range(2, m):
		dp[0][i] = dp[1][i - 1] * (k - 1) % mod
		dp[1][i] = (dp[0][i - 1] + dp[1][i - 1] * (k - 2)) % mod
		dp[2][i] = dp[2][i - 1] * (k - 1) % mod
		dp[3][i] = dp[2][i - 1] * k % mod
	odd = [(key, len(tuple(val))) for (key, val) in groupby(a[::2])]
	even = [(key, len(tuple(val))) for (key, val) in groupby(a[1::2])]
	ans = array('i', [1])
	for group in (odd, even):
		for (x, y, z) in zip(group, group[1:], group[2:]):
			if y[0] != -1:
				continue
			if x[0] == -2 and z[0] == -2:
				ans[0] = ans[0] * dp[3][y[1]] % mod
			elif x[0] == -2 or z[0] == -2:
				ans[0] = ans[0] * dp[2][y[1]] % mod
			elif x[0] == z[0]:
				ans[0] = ans[0] * dp[0][y[1]] % mod
			else:
				ans[0] = ans[0] * dp[1][y[1]] % mod
	print(ans[0])
main()


from functools import lru_cache
(N, K) = list(map(int, input().split()))
P = 998244353
A = [K + 100] + [int(a) for a in input().split()] + [K + j for j in range(1, 10)]
X = [[0, 0] for _ in range(N // 2 + 5)]
X[0][0] = 1
for i in range(1, N // 2 + 2):
	X[i][0] = X[i - 1][1]
	X[i][1] = (X[i - 1][0] * (K - 1) + X[i - 1][1] * (K - 2)) % P
Y = [[0, 0] for _ in range(N // 2 + 5)]
Y[0][1] = 1
for i in range(1, N // 2 + 2):
	Y[i][0] = Y[i - 1][1]
	Y[i][1] = (Y[i - 1][0] * (K - 1) + Y[i - 1][1] * (K - 2)) % P

def calc(l, a, b):
	if a > K and b > K:
		return K * pow(K - 1, l - 1, P) % P
	if a > K or b > K:
		return pow(K - 1, l, P)
	if a == b:
		return X[l + 1][0]
	else:
		return Y[l + 1][0]
l = 0
ans = 1
for j in range(2):
	pre = K + 50 + j
	for i in range(j, N + 5, 2):
		if A[i] == -1:
			l += 1
		elif l > 0:
			ans *= calc(l, pre, A[i])
			ans %= P
			pre = A[i]
			l = 0
		elif pre == A[i]:
			ans = 0
			break
		else:
			pre = A[i]
print(ans % P)


MOD = 998244353
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
ch = []
lt = None
for beg in (0, 1):
	for i in range(beg, n, 2):
		if a[i] == -1:
			if lt is None:
				lt = -1 if i - 2 < 0 else a[i - 2]
				sz = 0
			sz += 1
			if i + 2 >= n:
				ch.append((lt, -1, sz))
				lt = None
			elif a[i + 2] != -1:
				ch.append((lt, a[i + 2], sz))
				lt = None
ans = int(all((a[i] != a[i + 2] for i in range(n - 2) if a[i] != -1)))
for (lt, rt, sz) in ch:
	if sz == 1:
		cur = k if lt == -1 and rt == -1 else k - 1 if lt == -1 or rt == -1 or lt == rt else k - 2
	else:
		(eq, neq) = (1 if lt == -1 else 0, 1)
		for _ in range(sz - 1):
			(eq, neq) = (neq * (k - 1) % MOD, (neq * (k - 2) + eq) % MOD)
		cur = neq * (k - 1) + eq if rt == -1 else neq * (k - 1) if lt == rt else neq * (k - 2) + eq
	ans = ans * cur % MOD
print(ans)


import sys
input = sys.stdin.readline
mod = 998244353
(n, k) = map(int, input().split())
A = list(map(int, input().split()))
A0 = [A[i] for i in range(n) if i % 2 == 0]
A1 = [A[i] for i in range(n) if i % 2 == 1]
for j in range(1, len(A0)):
	if A0[j] != -1 and A0[j] == A0[j - 1]:
		print(0)
		sys.exit()
for j in range(1, len(A1)):
	if A1[j] != -1 and A1[j] == A1[j - 1]:
		print(0)
		sys.exit()
OPENLIST = []
j = 0
L = len(A0)
while j < L:
	OPEN = CLOSE = -10
	if A0[j] == -1:
		if j == 0:
			OPEN = -11
		else:
			OPEN = A0[j - 1]
		COUNT = 0
		while A0[j] == -1:
			COUNT += 1
			j += 1
			if j == L:
				CLOSE = -11
				break
		if OPEN == -11 and CLOSE == -11:
			OPENLIST.append([COUNT, 0])
		elif OPEN == -11 or CLOSE == -11:
			OPENLIST.append([COUNT, 1])
		elif A0[j] == OPEN:
			OPENLIST.append([COUNT, 3])
		else:
			OPENLIST.append([COUNT, 2])
	else:
		j += 1
j = 0
L = len(A1)
while j < L:
	OPEN = CLOSE = -10
	if A1[j] == -1:
		if j == 0:
			OPEN = -11
		else:
			OPEN = A1[j - 1]
		COUNT = 0
		while A1[j] == -1:
			COUNT += 1
			j += 1
			if j == L:
				CLOSE = -11
				break
		if OPEN == -11 and CLOSE == -11:
			OPENLIST.append([COUNT, 0])
		elif OPEN == -11 or CLOSE == -11:
			OPENLIST.append([COUNT, 1])
		elif A1[j] == OPEN:
			OPENLIST.append([COUNT, 3])
		else:
			OPENLIST.append([COUNT, 2])
	else:
		j += 1
ANS = 1
for (x, y) in OPENLIST:
	if y == 0:
		ANS = ANS * k * pow(k - 1, x - 1, mod) % mod
	elif y == 1:
		ANS = ANS * pow(k - 1, x, mod) % mod
	elif y == 2:
		DP0 = 0
		DP1 = 1
		for r in range(x + 1):
			NDP0 = DP1
			NDP1 = (DP0 * (k - 1) + DP1 * (k - 2)) % mod
			DP0 = NDP0
			DP1 = NDP1
		ANS = ANS * DP0 % mod
	else:
		DP0 = 1
		DP1 = 0
		for r in range(x + 1):
			NDP0 = DP1
			NDP1 = (DP0 * (k - 1) + DP1 * (k - 2)) % mod
			DP0 = NDP0
			DP1 = NDP1
		ANS = ANS * DP0 % mod
print(ANS)


class PalArray:
	P = 998244353

	def __init__(self, n, k, a):
		(self.n, self.k, self.a) = (n, k, a)
		self.dp = None

	def fast_pow(self, a, b):
		r = 1
		while b > 0:
			if b % 2 == 1:
				r = r * a % self.P
			a = a * a % self.P
			b = int(b / 2)
		return r

	def populate_dp(self):
		self.dp = [[0 for i in range(2)] for j in range(self.n + 1)]
		self.dp[1][0] = self.k - 2
		self.dp[1][1] = self.k - 1
		for i in range(2, self.n + 1):
			self.dp[i][0] = ((self.k - 2) * self.dp[i - 1][0] % self.P + self.dp[i - 1][1]) % self.P
			self.dp[i][1] = (self.k - 1) * self.dp[i - 1][0] % self.P

	def check_array(self, a):
		for i in range(1, len(a)):
			if a[i] != -1 and a[i] == a[i - 1]:
				return False
		return True

	def compute_count(self, a):
		check = False
		res = 1
		mis_cnt = 0
		lv = None
		for v in a:
			if v == -1:
				mis_cnt += 1
			else:
				if mis_cnt > 0:
					if not check:
						check = True
						res = res * self.fast_pow(self.k - 1, mis_cnt) % self.P
					else:
						res = res * self.dp[mis_cnt][int(lv == v)] % self.P
					mis_cnt = 0
				lv = v
				check = True
		if mis_cnt > 0:
			if lv is not None:
				res = res * self.fast_pow(self.k - 1, mis_cnt) % self.P
			else:
				res = res * self.fast_pow(self.k - 1, mis_cnt - 1) % self.P * self.k % self.P
		return res

	def num_combinations(self):
		self.populate_dp()
		a1 = [self.a[i] for i in range(0, self.n, 2)]
		a2 = [self.a[i] for i in range(1, self.n, 2)]
		cnt1 = self.compute_count(a1) * int(self.check_array(a1))
		cnt2 = self.compute_count(a2) * int(self.check_array(a2))
		return cnt1 * cnt2 % self.P
(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
print(PalArray(n, k, a).num_combinations())


mod = 998244353
maxn = 200002

def pow(a, e):
	if e <= 0:
		return 1
	ret = 1
	while e:
		if e & 1:
			ret = ret * a % mod
		a = a * a % mod
		e >>= 1
	return ret
(fn, fe) = ([1], [None])

def build(k):
	fn.append(k - 2)
	fe.append(k - 1)
	for i in range(2, maxn):
		fe.append((k - 1) * fn[i - 1] % mod)
		fn.append(((k - 1) * fn[i - 2] + (k - 2) * fn[i - 1]) % mod)

def getRanges(arr):
	(q, st, en) = ([], -1, -1)
	for (i, x) in enumerate(arr):
		if x == -1:
			if st == -1:
				st = en = i
			else:
				en = i
		elif st >= 0:
			q.append((st, en))
			(st, en) = (-1, -1)
	if arr[-1] == -1:
		q.append((st, en))
	return q

def getWays(arr, k):
	ans = 1
	for (st, en) in getRanges(arr):
		if st == 0 and en == len(arr) - 1:
			ans *= k * pow(k - 1, en - st)
		elif st == 0 or en == len(arr) - 1:
			ans *= pow(k - 1, en - st + 1)
		elif arr[st - 1] == arr[en + 1]:
			ans *= fe[en - st + 1]
		else:
			ans *= fn[en - st + 1]
		ans %= mod
	return ans

def incorrect(arr, n):
	for i in range(1, n - 1):
		if arr[i - 1] == arr[i + 1] and arr[i - 1] != -1:
			return True
	return False

def main():
	(n, k) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	if incorrect(arr, n):
		print(0)
		return
	build(k)
	even = [x for (i, x) in enumerate(arr) if i & 1 == 0]
	odd = [x for (i, x) in enumerate(arr) if i & 1 == 1]
	(e, o) = (getWays(even, k), getWays(odd, k))
	print(e * o % mod)
main()


import sys
sys.setrecursionlimit(10 ** 7)
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
dp1 = [1, 0]
dp2 = [1, K - 1]
for i in range(1 + N // 2):
	(d1, d2) = (dp1[-1], dp2[-1])
	dp1.append(d2)
	dp2.append(((K - 1) * d1 + (K - 2) * d2) % mod)
ans = 1
dif = (K - 2) * pow(K - 1, mod - 2, mod) % mod
AO = A[::2]
AE = A[1::2]
if all((a == -1 for a in AO)):
	ans = K * pow(K - 1, len(AO) - 1, mod) % mod
else:
	AO = [0] + AO + [0]
	mc = 0
	l = -2
	r = -2
	for (i, a) in enumerate(AO[1:], 1):
		if a == -1:
			if AO[i - 1] != -1:
				l = AO[i - 1]
			mc += 1
		else:
			r = a
			if AO[i - 1] == a:
				ans = 0
				break
			elif mc:
				if not l or not r:
					ans = ans * pow(K - 1, mc, mod) % mod
				elif l == r:
					ans = ans * dp2[mc] % mod
				else:
					ans = ans * (dp2[mc] * dif + dp1[mc]) % mod
			mc = 0
if all((a == -1 for a in AE)):
	ans = ans * K * pow(K - 1, len(AE) - 1, mod) % mod
else:
	AE = [0] + AE + [0]
	mc = 0
	l = -2
	r = -2
	for (i, a) in enumerate(AE[1:], 1):
		if a == -1:
			if AE[i - 1] != -1:
				l = AE[i - 1]
			mc += 1
		else:
			r = AE[i]
			if AE[i - 1] == a:
				ans = 0
				break
			if mc:
				if not l or not r:
					ans = ans * pow(K - 1, mc, mod) % mod
				elif l == r:
					ans = ans * dp2[mc] % mod
				else:
					ans = ans * (dp2[mc] * dif + dp1[mc]) % mod
			mc = 0
print(ans)


import sys
from sys import stdin, stdout
mod = 998244353
(n, k) = stdin.readline().split()
(n, k) = (int(n), int(k))

def hpow(x, y):
	if y == 0:
		return 1
	if y == 1:
		return x % mod
	a = hpow(x, y >> 1)
	a = a * a % mod
	return a * x % mod if y & 1 else a

def rev(x):
	return hpow(x, mod - 2)

def max(x, y):
	return x if x >= y else y
revk = rev(k)

def cal(l, x, y):
	rr = 1
	if not x and (not y):
		rr = k * hpow(k - 1, l - 1) % mod
		return rr
	if not y:
		(x, y) = (y, x)
	if not x:
		rr = k
		for i in range(l - 1):
			rr = rr * (k - 1) % mod
		return rr * revk % mod * (k - 1) % mod
	if x == y:
		f = [[k - 1, 0]]
		for i in range(1, l):
			f.append([(f[i - 1][1] * (k - 1) % mod + f[i - 1][0] * (k - 2) % mod) % mod, f[i - 1][0]])
		return f[l - 1][0]
	f = [[k - 2, 0, 1]]
	for i in range(1, l):
		f.append([((f[i - 1][1] + f[i - 1][2]) * (k - 2) % mod + f[i - 1][0] * max(0, k - 3) % mod) % mod, (f[i - 1][2] + f[i - 1][0]) % mod, (f[i - 1][1] + f[i - 1][0]) % mod])
	return (f[l - 1][0] + f[l - 1][1]) % mod
a = [int(x) for x in stdin.readline().split()]
(m1, m2) = (0, 0)
b = [0]
c = [0]
for i in range(n):
	if i & 1:
		b.append(a[i])
	else:
		c.append(a[i])
m1 = len(b) - 1
m2 = len(c) - 1
res = 1
for i in range(1, m1 + 1):
	if b[i] > 0 and b[i] == b[i - 1]:
		stdout.write(str(0))
		sys.exit()
for i in range(1, m2 + 1):
	if c[i] > 0 and c[i] == c[i - 1]:
		stdout.write(str(0))
		sys.exit()
j = -1
for i in range(1, m1 + 1):
	if b[i] == -1:
		if j < 0:
			j = i
		if i >= m1 or b[i + 1] != -1:
			res = res * cal(i - j + 1, 0 if j <= 1 else b[j - 1], 0 if i >= m1 else b[i + 1]) % mod
			j = -1
j = -1
for i in range(1, m2 + 1):
	if c[i] == -1:
		if j < 0:
			j = i
		if i >= m2 or c[i + 1] != -1:
			res = res * cal(i - j + 1, 0 if j <= 1 else c[j - 1], 0 if i >= m2 else c[i + 1]) % mod
			j = -1
stdout.write(str(res))


(n, k) = map(int, input().strip().split())
l = list(map(int, input().strip().split()))
test = True
md = 998244353
evens = [0]
odds = [0]
for i in range(n):
	if i % 2:
		odds.append(l[i])
	else:
		evens.append(l[i])
evens.append(-10)
odds.append(-10)
segs = []
l = len(odds)
cont = False
test = True
for i in range(l):
	if odds[i] == -1 and cont == False:
		a = i - 1
		cont = True
	elif odds[i] != -1 and cont == True:
		cont = False
		b = i
		segs.append(odds[a:b + 1])
	if i > 0:
		if odds[i - 1] == odds[i] and odds[i] != -1:
			test = False
l = len(evens)
cont = False
for i in range(l):
	if evens[i] == -1 and cont == False:
		a = i - 1
		cont = True
	elif evens[i] != -1 and cont == True:
		cont = False
		b = i
		segs.append(evens[a:b + 1])
	if i > 0:
		if evens[i - 1] == evens[i] and evens[i] != -1:
			test = False
ans = 1
for seg in segs:
	l = len(seg) - 2
	dp = [[0, 0] for i in range(l)]
	a = seg[-1]
	b = seg[0]
	if b == 0:
		dp[0][0] = 1
		dp[0][1] = k - 1
	elif b == a:
		dp[0][0] = 0
		dp[0][1] = k - 1
	elif b != a:
		dp[0][0] = 1
		dp[0][1] = k - 2
	for i in range(1, l):
		dp[i][0] = dp[i - 1][1] % md
		dp[i][1] = (dp[i - 1][0] * (k - 1) + dp[i - 1][1] * (k - 2)) % md
	if a == -10:
		ans *= dp[l - 1][0] + dp[l - 1][1]
	else:
		ans *= dp[l - 1][1]
	ans %= md
if test == False:
	print(0)
else:
	print(ans)


def solve1(a, l, r, k, mod):
	n = len(a)
	if l == 0 and r == n:
		return k * (k - 1) ** (n - 1)
	if l == 0 or r == n:
		return (k - 1) ** (r - l)
	x = a[l - 1]
	y = a[r]
	dp0 = [0] * (r - l)
	dp1 = [0] * (r - l)
	if x != y:
		dp0[0] = k - 2
		dp1[0] = 1
	else:
		dp0[0] = k - 1
		dp1[0] = 0
	for i in range(1, r - l):
		dp0[i] = dp0[i - 1] * (k - 2) + dp1[i - 1] * (k - 1)
		dp1[i] = dp0[i - 1]
		dp0[i] %= mod
		dp1[i] %= mod
	return dp0[-1]

def solve(a, k, mod):
	n = len(a)
	res = 1
	i = 0
	while i < n:
		if i < n - 1 and a[i] != -1 and (a[i] == a[i + 1]):
			return 0
		if a[i] != -1:
			i += 1
			continue
		j = i
		while j < n and a[i] == a[j]:
			j += 1
		res *= solve1(a, i, j, k, mod)
		i = j
	return res
(n, k) = map(int, input().split())
src = list(map(int, input().split()))
e = src[0::2]
o = src[1::2]
mod = 998244353
print(solve(e, k, mod) * solve(o, k, mod) % mod)