408685: GYM103261 L Not Our Problem

Memory Limit:0 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

L. Not Our Problemtime limit per test2 secondsmemory limit per test256 mebibytesinputstandard inputoutputstandard output

Someone (not me!) calls an array of length $$$n$$$ consisting of non-negative integers good if and only if $$$a_{i} \cdot a_{i + 1} \cdot \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 $$$998\,244\,353$$$.

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, which means that it needs to be filled, or between $$$0$$$ and $$$10^{18}$$$, inclusive.

Output

If the number of ways is infinite, print $$$-1$$$, otherwise print the number of ways modulo $$$998\,244\,353$$$.

ExamplesInput
4 100
-1 7 2 -1
Output
104
Input
4 100
10 -1 -1 1
Output
240
Input
1 0
-1
Output
-1
Input
2 10
10 10
Output
0

加入题单

上一题 下一题 算法标签: