### Problem Statement

John and Brus are studying string theory at the university. According to Brus, a string is called lucky if no two consecutive characters are equal. John 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.

### Definition

 Class: TheLuckyString Method: count Parameters: String Returns: int Method signature: int count(String s) (be sure your method is public)

### Constraints

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

### Examples

0)

 `"ab"`
`Returns: 2`
 Two lucky strings - "ab" and "ba".
1)

 `"aaab"`
`Returns: 0`
 It's impossible to construct a lucky string.
2)

 `"aabbbaa"`
`Returns: 1`
 "abababa" is the only lucky string that can be generated.
3)

 `"abcdefghij"`
`Returns: 3628800`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10180

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13519&pm=10180

Vasyl[alphacom]

#### Testers:

PabloGilberto , Olexiy , ivan_metelsky

#### Problem categories:

Simple Search, Iteration