Działanie odejmowania nie jest łączne, np (5-2)-1=2, natomiast 5-(2-1)=4, a zatem (5-2)-1<>5-(2-1). Wynika stąd, że wartość wyrażenia postaci 5-2-1 zależy od kolejności wykonywania odejmowań. Zwykle przy braku nawiasów przyjmuje się, że wykonujemy działania w kolejności od lewej do prawej, czyli wyrażenie 5-2-1 jest równoważne wyrażeniu (5-2)-1.

Mamy dane wyrażenie postaci:

x₁ +/- x₂ +/- ... +/- x_n

gdzie +/- oznacza + (plus) lub - (minus), a x₁,x₂,...,x_n oznaczają (parami) różne zmienne. Chcemy w wyrażeniu postaci:

x₁-x₂-...-x_n

tak rozstawić n-1 par nawiasów, aby jednoznacznie określić kolejność wykonywania odejmowań i jednocześnie uzyskać wyrażenie równoważne danemu. Na przykład, chcąc uzyskać wyrażenie równoważne wyrażeniu:

x₁-x₂-x₃+x₄+x₅-x₆+x₇

możemy w:

x₁-x₂-x₃-x₄-x₅-x₆-x₇

rozmieścić nawiasy w następujący sposób:

(((x₁-x₂)-((x₃-x₄)-x₅))-(x₆-x₇)).

Uwaga: Interesują nas tylko wyrażenia w pełni i poprawnie ponawiasowane. Wyrażeniem w pełni i poprawnie ponawiasowanym jest

• albo pojedyncza zmienna,
• albo wyrażenie postaci (w₁-w₂), w którym w₁ i w₂, to w pełni i poprawnie ponawiasowane wyrażenia.

Nieformalnie mowiąc, nie interesują nas wyrażenia, w których występują na przykład konstrukcje postaci: (), (x_i), ((...)) lub x₁-(x₂-x₃) nie jest w pełni ponawiasowane, ponieważ brakuje zewnętrznych nawiasów.

Zadanie

Napisz program, który:

• wczyta z pliku tekstowego naw.in opis danego wyrażenia postaci x₁ +/- x₂ +/- ... +/- x_n,
• obliczy na ile różnych sposobów (modulo 1 000 000 000) można rozstawić n-1 par nawiasów w wyrażeniu x₁-x₂-...-x_n tak, aby jednoznacznie określić kolejność wykonywania odejmowań i jednocześnie uzyskać wyrażenie równoważne danemu,
• zapisze wynik w pliku tekstowym naw.out.

Wejście

W pierwszym wierszu pliku tekstowego naw.in zapisana jest jedna liczba całkowita n, 2<=n<=5000. Jest to liczba zmiennych w danym wyrażeniu. W każdym z kolejnych n-1 wierszy jest zapisany jeden znak, + lub -. W i-tym wierszu zapisany jest znak występujący w danym wyrażeniu między x_i-1 a x_i.

Wyjście

Twój program powinien zapisać w pierwszym wierszu pliku tekstowego naw.out jedną liczbę całkowitą równą ilości różnych sposobów (modulo 1 000 000 000), na jakie można rozstawić n-1 par nawiasów w wyrażeniu x₁-x₂-...-x_n tak, aby jednoznacznie określić kolejność wykonywania odejmowań i jednocześnie uzyskać wyrażenie równoważne danemu.

Przykład

Dla pliku wejściowego naw.in:

7
-
-
+
+
-
+

poprawną odpowiedzią jest plik wyjściowy naw.out:

3