Description

DK and MoonLight are studying string theory at the university. According to DK, a string is called lucky if no two consecutive characters are equal. MoonLight is analyzing a string s, and he wants to know how many distinct lucky strings can be generated by reordering the letters in s. If s is a lucky string in its original ordering, it should also be considered in the count.

Input

s will contain between 1 and 12 characters, inclusive.Each character of s will be a lowercase letter ('a' - 'z').

Output

For each test case, output the number of lucky string that can be made.

Sample

Input

ab
aaabb
abcdefghij

Output

2
1
3628800

Source: moonlight