Lucky Strings

Time limit

Memory limit

256 MB

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.