Problem description

Tym razem, dla uproszczenia zadania, w treści nie pojawi się rozbudowana historyjka.

Dany jest ciąg składający się z nieujemnych liczb całkowitych oraz znaków zapytania – ?, a także nieujemna liczba całkowita C. Naszym celem jest zamiana wszystkich znaków zapytania na nieujemne liczby całkowite tak, aby spełniony był warunek: A_i ⋅ A_i + 1 ⋅ min (A_i,A_i + 1) ≤ C dla 1 ≤ i < N.

Twoim zadaniem jest obliczenie liczby możliwych ciągów, które po takiej zamianie mogą powstać, modulo 998 244 353. Jeśli liczba możliwych ciągów jest nieskończona, należy wypisać -1.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite N i C, będące odpowiednio długością ciągu oraz stałą, o której mowa w zadaniu. W drugim wierszu wejścia znajduje się ciąg A₁, A₂, …, A_N, gdzie każdy element tego ciągu jest nieujemną liczbą całkowitą, albo wartością -1, co dla uproszczenia reprezentuje znak zapytania.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć liczba ciągów spełniających warunki zadania, modulo 998 244 353, lub wartość -1, jeśli ta liczba jest nieskończona.

Ograniczenia

1 ≤ N ≤ 1 000 000, 0 ≤ C ≤ 10¹⁸, -1 ≤ A_i ≤ 10¹⁸.

W testach wartych łącznie 50% maksymalnej punktacji zachodzi: C ≤ 1 000 000.

Przykład

4 10
1 -1 2 -1

9

3 10
2 2 3

0

3 5
-1 -1 -1

-1