Mamy wystarczająco dużo kart z każdą z liczb od $1$ do $34$. Kilka z nich ułożono w rzędzie, a następnie zapisano kolejno znajdujące się na nich liczby. Na przykład dla poniższego układu kart otrzymujemy zapis $27123$.

27 | 1 | 23

Później, próbując ponownie ułożyć karty zgodnie z zapisanymi cyframi, odkryto, że może istnieć kilka sposobów ich ułożenia.

Na przykład dla $27123$ istnieje sześć różnych sposobów przedstawionych poniżej.

2 | 7 | 1 | 2 | 3
27 | 1 | 2 | 3
2 | 7 | 12 | 3
2 | 7 | 1 | 23
27 | 12 | 3
27 | 1 | 23

Dany jest zapis liczb z kart w kolejności ich ułożenia. Chcemy odtworzyć układ kart tak jak powyżej. Napisz program obliczający łączną liczbę możliwych układów kart.

Wejście

W pierwszym wierszu podano zapis liczb z kart w kolejności ich ułożenia, składający się z co najwyżej $40$ cyfr.

Wyjście

Wypisz liczbę możliwych układów kart.

Przykład

Wejście 1

27123

Wyjście 1

6

Wejście 2

77777777777777777777

Wyjście 2

1