Problem 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
| Wejście | Wyjście | |
|
|
| Wejście | Wyjście | |
|
|