Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Vasya and Array

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputVasya has got an array consisting of $$$n$$$ integers, and two integers $$$k$$$ and $$$len$$$ in addition. All numbers in the array are either between $$$1$$$ and $$$k$$$ (inclusive), or equal to $$$-1$$$. The array is good if there is no segment of $$$len$$$ consecutive equal numbers.

Vasya will replace each $$$-1$$$ with some number from $$$1$$$ to $$$k$$$ (inclusive) in such a way that the resulting array is good. Tell him the number of ways to do this replacement. Since the answer may be large, print it modulo $$$998244353$$$.

Input

The first line contains three integers $$$n, k$$$ and $$$len$$$ ($$$1 \le n \le 10^5, 1 \le k \le 100, 1 \le len \le n$$$).

The second line contains $$$n$$$ numbers — the array. Each number is either $$$-1$$$ or between $$$1$$$ and $$$k$$$ (inclusive).

Output

Print one integer — the number of ways to replace each $$$-1$$$ with some number from $$$1$$$ to $$$k$$$ (inclusive) so the array is good. The answer may be large, so print it modulo $$$998244353$$$.

Examples

Input

5 2 3 1 -1 1 -1 2

Output

2

Input

6 3 2 1 1 -1 -1 -1 -1

Output

0

Input

10 42 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

Output

645711643

Note

Possible answers in the first test:

- $$$[1, 2, 1, 1, 2]$$$;
- $$$[1, 2, 1, 2, 2]$$$.

There is no way to make the array good in the second test, since first two elements are equal.

There are too many answers in the third test, so we won't describe any of them.

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/26/2019 08:01:12 (e3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|