1435 . 小卷的訓練
TopCoder
Tags
Description
小卷是一個自然番茄大學（Natural Tomato University, NTU）的來自海鮮王國的交換生，正如他的名字一樣，從小就在卷。
小卷從小的夢想就是成為 ICPC（International Cultivation and Planting Contest，國際種植與栽培競賽）的競賽選手，在聽聞 小黃瓜的故事 之後，小卷也去找了一個教練。
教練在聽完小卷的夢想之後立刻開始著手操辦，但是由於小卷的技術尚未成熟，教練決定給他一個特訓。特訓總共有 $N$ 天，為了防止技術生疏，不能有幾天過度荒廢（當然也不能有田地過度荒廢，畢竟是栽培競賽），因此教練規定接下來的每 $D$ 天小卷剛好要種 $B$ 棵植物。
現在小卷已經對他接下來的 $N$ 天有一些規劃了，他用一個長度是 $N$ 的序列 $A_i$ 表示，如果 $A_i = -1$ 那他對第 $i$ 天沒有規劃，否則第 $i$ 天他會剛好種 $A_i$ 棵植物。小卷想要知道在這個情況下他有多少種把 $-1$ 填上非負整數的方式使得他滿足教練給的條件，由於數字可能很大，請模 $998244353$ 後輸出。
Input Format
輸入共有兩行，第一行是三個整數 $N$, $D$, $B$
第二行有 $N$ 個整數 $A_i$。
- $1 \leq D \leq N \leq 5 \times 10^ 5$
- $1 \leq B \leq 5 \times 10^ 6$
- $-1 \leq A_i \leq B$
Output Format
輸出一個整數，代表小卷還有多少種方法填上非負整數，由於數字可能很大，請模 $998244353$ 後輸出。
Sample Input 1
4 3 5 3 -1 -1 -1
Sample Output 1
3
Sample Input 2
8 4 20 -1 -1 -1 -1 4 -1 -1 -1
Sample Output 2
153
Hints
在第一筆範例測試資料中，所有小卷的合法的把 $-1$ 填上非負整數的方法如下：
- $[3, 0, 2, 3]$
- $[3, 1, 1, 3]$
- $[3, 2, 0, 3]$
總共 $3$ 種。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資。 | 0 |
| 2 | 0~40 | 無特別限制。 | 100 |