Es gibt ausreichend viele Karten mit jeder der Zahlen von $1$ bis $34$. Einige davon wurden in einer Reihe angeordnet, und ihre Zahlen wurden der Reihe nach aufgeschrieben. Wenn die Karten beispielsweise wie unten angeordnet sind, ergibt das Aufschreiben ihrer Zahlen der Reihe nach $27123$.

27 | 1 | 23

Als man später versuchte, die Karten passend zur aufgeschriebenen Ziffernfolge erneut anzuordnen, stellte man fest, dass es dafür mehrere Möglichkeiten geben kann.

Für $27123$ gibt es beispielsweise die folgenden sechs verschiedenen Möglichkeiten.

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

Gegeben sind die der Reihe nach aufgeschriebenen Zahlen der Karten. Daraus soll wie oben die Anordnung der Karten rekonstruiert werden. Schreibe ein Programm, das die Gesamtzahl der möglichen Kartenanordnungen bestimmt.

Eingabe

Die erste Zeile enthält die der Reihe nach aufgeschriebenen Zahlen der Karten als Folge von höchstens $40$ Ziffern.

Ausgabe

Gib die Anzahl der möglichen Kartenanordnungen aus.

Beispiele

Eingabe 1

27123

Ausgabe 1

6

Eingabe 2

77777777777777777777

Ausgabe 2

1