Not Our Problem

Time limit2sMemory limit512 MB

Summary

Count the ways to fill the -1 entries so every adjacent pair satisfies a_i * a_{i+1} * min(a_i, a_{i+1}) <= C, or print -1 if there are infinitely many.

Level: Hard8 of 10
Topics: Dynamic programming, Math
Solved: No attempts yet

Problem

Someone (not me!) calls an array of length $n$ consisting of non-negative integers good if and only if $a_i a_{i+1} \min(a_i, a_{i+1}) \le C$ holds for all $1 \le i < n$ .

Someone else (we have nothing to do with them!) gives you an array of length $n$ with some blank positions. Calculate the number of ways to fill in the blank positions so that the array is good, or determine that there are infinitely many ways. If the answer is finite, print it modulo $998244353$ .

Input

The first line contains two integers $n$ and $C$ ( $1 \le n \le 10^6$ , $0 \le C \le 10^{18}$ ), the length of the array and the constraint on the product.

The second line contains the array $a$ . Each element is either $-1$ , meaning it needs to be filled, or an integer between $0$ and $10^{18}$ , inclusive.

Output

If the number of ways is infinite, print $-1$ . Otherwise, print the number of ways modulo $998244353$ .

Examples4

Example 1
Input
```
4 100
-1 7 2 -1
```
Expected output
```
104
```
Example 2
Input
```
4 100
10 -1 -1 1
```
Expected output
```
240
```
Example 3
Input
```
1 0
-1
```
Expected output
```
-1
```
Example 4
Input
```
2 10
10 10
```
Expected output
```
0
```