問題文

長さ $N$ の小文字アルファベットのみからなる文字列 $S$ が与えられます。$S$ に対して以下の $2$ 種類の操作を行うことができます

操作 $1:$ 整数 $i ~~ (1 \leq i \leq N - 1) ~$ を選び、 $S_i$ と $S_{i+1}$ を入れ替える$\\$ 操作 $2:$ 整数 $i ~~ (1 \leq i \leq N - 2) ~$ を選び、 $S_i$ と $S_{i+2}$ を入れ替える

操作 $1$ を $1$ 回以下行った後、操作 $2$ を任意の回数行えます。$\\$ 操作後の文字列として考えられるものが何通りか求めてください。ただし、答えは非常に大きくなる可能性があるので $10 ^ 9 + 7$ で割った余りを出力してください

制約

• $1 \leq N \leq 10 ^ 5$

入力

入力はすべて整数である。

N
S

出力

計算結果を一行に出力せよ。

サンプル

3
aab

3

"aab" の並び替えすべてを作ることができます

15
mmacontesteight

66867193

$10 ^ 9 + 7$ で割った余りを出力することに注意してください。