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: interview

Starter code:

Solutions:
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)]
# A = [K+100] + [1, 2] + [-1 for a in range(N-4)] + [3,4]+ [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]:
            # print(A)
            ans = 0
            break
        else:
            pre = A[i]

print(ans%P)


import sys
input = sys.stdin.readline

mod=998244353

n,k=list(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)
        return

for j in range(1,len(A1)):
    if A1[j]!=-1 and A1[j]==A1[j-1]:
        print(0)
        return

        
    
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])
        else:
            if 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])
        else:
            if 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)
        


        
        



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)
    # print(re)
    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
        else:
            if 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)



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)

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 = list(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)


3.7

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)
            return

    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)


3.7

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)
            return

    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)


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)

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((yi[i-1])*(k-1)%998244353)
    yi.append(((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
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)

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
        else:
            if 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 = list(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)



def __starting_point():
    main()



__starting_point()

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
        else:
            if 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 = list(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)



def __starting_point():
    main()



__starting_point()

# AC
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()

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())





import sys
from sys import stdin, stdout  

mod = 998244353

#fileIO = open("a.inp", "r")

n,k = stdin.readline().split() #fileIO.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]
    
    # final case -> x ... y

    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()]

#fileIO.close()

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

# process array b & c separately

#fileIO = open("a.out","w")

for i in range(1,m1 + 1) :
    if(b[i] > 0 and b[i] == b[i - 1]) :
        stdout.write(str(0)) #fileIO.write(str(0))
        return
for i in range(1,m2 + 1) :
    if(c[i] > 0 and c[i] == c[i - 1]) :
        stdout.write(str(0))
        return

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))
#fileIO.close()


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
        else:
            if 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
        else:
            if 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)