Treść zadania
JOI-kun jest uczniem $1$. klasy szkoły podstawowej. JOI-kun bardzo lubi dodawanie i odejmowanie, których dopiero co się nauczył, więc gdy widzi ciąg ustawionych obok siebie cyfr, bawi się w tworzenie równości, wstawiając = pomiędzy ostatnie $2$ cyfry, a pomiędzy pozostałe sąsiednie cyfry zawsze wstawiając + lub -. Na przykład z ciągu 8 3 2 4 8 7 2 4 0 8 8 może utworzyć równość 8+3-2-4+8-7-2-4-0+8=8.
Po utworzeniu równości JOI-kun wykonuje obliczenia, aby sprawdzić, czy jest ona poprawna. JOI-kun nie zna jednak jeszcze liczb ujemnych i nie potrafi wykonywać obliczeń na liczbach przekraczających $20$. Dlatego spośród poprawnych równości tylko te, w których podczas obliczania lewej strony od lewej do prawej wszystkie pojawiające się po drodze wyniki są nie mniejsze niż $0$ i nie większe niż $20$, są poprawnymi równościami, które JOI-kun potrafi zweryfikować. Na przykład 8+3-2-4-8-7+2+4+0+8=8 jest poprawną równością, ale ponieważ pojawiające się w trakcie obliczeń 8+3-2-4-8 jest liczbą ujemną, JOI-kun nie jest w stanie sprawdzić, czy ta równość jest poprawna.
Mając dany na wejściu ciąg cyfr, napisz program wyznaczający liczbę poprawnych równości, które JOI-kun może utworzyć i zweryfikować.
Wejście
Plik wejściowy składa się z $2$ wierszy. W $1$. wierszu znajduje się liczba całkowita $N$ ($3 \le N \le 100$) oznaczająca liczbę ustawionych cyfr. W $2$. wierszu znajduje się $N$ liczb całkowitych nie mniejszych niż $0$ i nie większych niż $9$, oddzielonych spacjami.
W $60\%$ danych wejściowych liczba poprawnych równości, które JOI-kun może utworzyć i zweryfikować, nie przekracza $2^{31}-1$. Ponadto we wszystkich danych wejściowych liczba poprawnych równości, które JOI-kun może utworzyć i zweryfikować, nie przekracza $2^{63}-1$.
Wyjście
Wypisz w $1$ wierszu liczbę całkowitą oznaczającą liczbę poprawnych równości, które JOI-kun może utworzyć i zweryfikować.
Przykłady wejścia/wyjścia
Przykład wejścia 1
11 8 3 2 4 8 7 2 4 0 8 8
Przykład wyjścia 1
10
Przykład wejścia 2
40 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1
Przykład wyjścia 2
7069052760
W Przykładzie wejścia $1$ JOI-kun może utworzyć i zweryfikować następujące $10$ poprawnych równości:
8+3-2-4+8-7-2-4-0+8=88+3-2-4+8-7-2-4+0+8=88+3+2+4-8-7+2-4-0+8=88+3+2+4-8-7+2-4+0+8=88+3+2-4+8-7+2+4-0-8=88+3+2-4+8-7+2+4+0-8=88-3+2+4-8+7+2+4-0-8=88-3+2+4-8+7+2+4+0-8=88-3+2-4+8+7+2-4-0-8=88-3+2-4+8+7+2-4+0-8=8
Dlatego program powinien wypisać $10$.
W Przykładzie wejścia $2$ zwróć uwagę, że odpowiedź nie mieści się w zakresie $32$-bitowej liczby całkowitej ze znakiem.
(Dopisek z dnia $21$.$2$.$2015$ r.) Dzięki zgłoszeniu od użytkownika okazało się, że wśród równości w wyjaśnieniu do Przykładu wejścia $1$ znajdował się błąd. Został on już poprawiony. Jako $5$. równość widniało 8+3-2-4+8-7+2+4-0-8=8, co zostało poprawione na 8+3+2-4+8-7+2+4-0-8=8. Ponadto jako $6$. równość widniało 8+3-2-4+8-7+2+4+0-8=8, co zostało poprawione na 8+3+2-4+8-7+2+4+0-8=8.