Lucky Strings

Interview

Time limit2sMemory limit256 MB

Summary

Count the distinct rearrangements of a short string (length up to 10) that have no two adjacent equal characters.

Level: Medium4 of 10
Topics: Backtracking, Combinatorics, String
Solved: No attempts yet

Problem

Minsik and Junyoung are studying strings in their room. Call a string lucky if no two adjacent characters in it are the same.

Junyoung starts analyzing a string S. He wants to know how many different lucky strings can be made by rearranging all characters of S. If the original string S is already lucky, it is also counted.

Input

The first line contains the string S. The length of S is at most 10, and S consists only of lowercase English letters.

Output

Print the number of different lucky strings that can be obtained by rearranging the characters of S.

Examples4

Example 1
Input
```
aabbbaa
```
Expected output
```
1
```
Example 2
Input
```
ab
```
Expected output
```
2
```
Example 3
Input
```
aaab
```
Expected output
```
0
```
Example 4
Input
```
abcdefghij
```
Expected output
```
3628800
```