Masterchef

No Masterchef os participantes são desafiados a preparar os pratos propostos pelos juízes. A receita original de cada prato é representada por uma sequência de ingredientes, mas cada participante deve reinterpretá-la dando seu toque pessoal no preparo. Isto significa que o participante pode trocar, quantas vezes achar necessário, a ordem de preparo de dois ingredientes da sequência.

Por exemplo, se a receita original é dada por sal, pimenta, sal, isto é, SPS, há duas reinterpretações possíveis: SSP e PSS.

Determine o número de reinterpretações possíveis para a receita original.

Entrada

A primeira linha da entrada contém o número $N$ ($1\leq N\leq 10$) de ingredientes da receita original.

A segunda linha traz a sequência de preparo destes ingredientes, na forma de uma string $S$ formada por $N$ caracteres alfabéticos maiúsculos.

Saída

Imprima, em uma linha, o número de reinterpretações possíveis para a receita original.

Exemplo de entrada 1

3
SPS

Exemplo de saída 1

2

Exemplo de entrada 2

2
PP

Exemplo de saída 2

0

Exemplo de entrada 3

5
SPPOS

Exemplo de saída 3

29