#描述#
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.

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

##输出格式##
For each test case, output the number of lucky string that can be made.

#样例1#
##样例输入1##

ab
aaabb
abcdefghij

##样例输出1##

2
1
3628800

#限制#
1000ms
32768KB

#提示#

#来源#
moonlight