「『庭院深深深幾許』同字不相鄰有幾種排法？」── 全台灣的高中數學老師 「『山外青山樓外樓』同字不相鄰有幾種排法？」── 雜牌的數學測驗卷 你受夠這種算出來毫無用處的數學習題了，決定寫一個程式來解決這類問題。 為了處理方便，輸入句子中的每個字會被對應到大寫字母。

輸入格式

輸入的第一行包含一個正整數 N(N = 1~8)，代表字串的長度。 第二行有一個字串S，由大寫英文字母組成。  

輸出格式

輸出一個整數於一行，代表同字不相鄰的排列數。

範例輸入 1

5
ABCDE

範例輸出 1

120

範例輸入 2

4
AAAB

範例輸出 2

0

範例輸入 3

7
ABCCCDE

範例輸出 3

240