Contest problemset description

Jasio znalazł na strychu zestaw małego programisty. Jak wiadomo, kiedyś nie było komputerów i programowano na kartce, dlatego zestaw ten jest dosyć specyficzny. Składa się on z bardzo długiej taśmy oraz ołówka. Taśma to wąski pasek papieru podzielony na nieparzystą liczbę komórek, w każdej z nich początkowo znajduje się wartość 0. Natomiast ołówek to po prostu zwykły ołówek z gumką, który służy do zmazywania i zapisywania wartości na taśmie, na początku ,,wskazuje’’ on na środkową komórkę taśmy.

Programy przeznaczone na taki zestaw kodowano za pomocą ciągu symboli, a następnie wykonywano ręcznie. Na potrzeby zadania założymy, że w naszych programach będziemy używać wyłącznie czterech symboli:

• + – zwiększ wartość komórki, na którą wskazuje ołówek o 1,
• - – zmniejsz wartość komórki, na którą wskazuje ołówek o 1,
• > – przesuń ołówek o jedną komórkę w prawo,
• < – przesuń ołówek o jedną komórkę w lewo.

Jasio znalazł także kilka przykładowych programów, ale podejrzewa, że zostały one napisane nieoptymalnie. Wydaje mu się, że każdy z nich można by nieco skrócić, pozostawiając tylko pewien spójny fragment instrukcji.

Twoim zadaniem jest obliczenie, na ile sposobów dany program może zostać skrócony, tak aby wynik wykonania się nie zmienił. Przez wynik wykonania rozumiemy tylko stan liczb na taśmie, ignorujemy pozycję końcową ołówka. Możesz założyć, że taśma jest na tyle długa, że ołówek nigdy poza nią nie wyjdzie.

Wejście

W pierwszym wierszu wejścia znajduje się dodatnia liczba całkowita N, będąca długością programu. W drugim wierszu znajduje się ciąg N symboli opisujących program.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć liczba spójnych fragmentów programu, których wynik wykonania jest taki sam, jak całego programu.

Ograniczenia

1 ≤ N ≤ 250 000.

W testach wartych łącznie 30% maksymalnej punktacji zachodzi: N ≤ 1000.

Przykład

5
+>+<-

3

5
+>+-<

5

Pan Wiesio znany jest z tego, że ,,robi u siebie jak u siebie’’, dlatego przed następnym remontem chciałby dowiedzieć się, ile uda mu się na nim zaoszczędzić, wykonując go samemu. Remont polega na położeniu dokładnie M metrów kwadratowych płytek, oczywiście bez krzyżaczków. Na Grochowie dostępnych jest N majstrów, i-ty z nich ma cennik składający się z trzech liczb:

• D_i – opłata początkowa,
• C_i – koszt położenia jednego metra kwadratowego płytek,
• Z_i – limit powyżej którego majster nie jest w stanie już pracować, tzn. może on położyć co najwyżej Z_i metrów kwadratowych płytek.

Twoim zadaniem jest obliczenie jaką kwotę zaoszczędzi pan Wiesio, czyli ile wyniósłby minimalny koszt wykonania remontu. Możesz założyć, że dane są dobrane tak, że wykonanie remontu jest zawsze możliwe.

Wejście

W pierwszym wierszu wejścia znajdują się dwie dodatnie liczby całkowite N i M, będące odpowiednio liczbą majstrów oraz powierzchnią konieczną do wyremontowania. W kolejnych N wierszach znajduje się opis cenników majstrów. Każdy cennik składa się z trzech liczb całkowitych: D_i, C_i oraz Z_i, tak jak opisano w treści zadania.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita, będąca minimalnym kosztem wykonania remontu.

Ograniczenia

1 ≤ N, M ≤ 4000, 1 ≤ D_i, C_i ≤ 10⁷, 1 ≤ Z_i ≤ M.

Przykład

5 20
5 2 5
1 4 4
3 2 5
9 1 4
2 4 5

68

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