Há cartões em quantidade suficiente com cada um dos números de $1$ a $34$. Alguns deles foram dispostos numa fila e os seus números foram escritos por ordem. Por exemplo, se os cartões estiverem dispostos como abaixo, escrever os seus números por ordem resulta em $27123$.

27 | 1 | 23

Mais tarde, ao tentar dispor novamente os cartões de acordo com o que tinha sido escrito, descobriu-se que poderia haver várias maneiras de o fazer.

Por exemplo, para $27123$, existem seis maneiras diferentes, como se mostra abaixo.

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

Dada a escrita dos números dos cartões por ordem, queremos reconstruir a disposição dos cartões como acima. Escreva um programa que calcule o número total de disposições possíveis dos cartões.

Entrada

A primeira linha contém a escrita dos números dos cartões por ordem, composta por no máximo $40$ algarismos.

Saída

Imprima o número de disposições possíveis dos cartões.

Exemplos

Entrada 1

27123

Saída 1

6

Entrada 2

77777777777777777777

Saída 2

1