There are sufficiently many cards bearing each of the numbers from $1$ to $34$. Some of these cards were arranged in a row, and their numbers were written down in order. For example, if the cards are arranged as below, writing their numbers in order gives $27123$.

27 | 1 | 23

Later, when trying to arrange the cards again to match what was written down, it was discovered that there could be several ways to do so.

For example, for $27123$, there are six different ways, as shown below.

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

Given the numbers on the cards written down in order, we want to reconstruct the arrangement of cards as above. Write a program to find the total number of possible arrangements of cards.

Input

The first line contains the numbers on the cards written down in order, consisting of at most $40$ digits.

Output

Print the number of possible arrangements of cards.

Examples

Input 1

27123

Output 1

6

Input 2

77777777777777777777

Output 2

1