SPOJ Brasil

Vira! é um jogo individual que se inicia com N peças igualmente espaçadas em uma linha. Cada peça do Vira! possui dois lados, sendo um branco e um preto; assim, ao virar uma peça, alterna-se a cor que está sendo mostrada entre branco e preto. A figura abaixo ilustra um possível arranjo com 5 peças, duas mostrando o lado branco e duas mostrando o lado preto.

Um movimento consiste em retirar uma peça preta – criando um espaço – e inverter as peças vizinhas à retirada. Sendo assim, dependendo do número de peças vizinhas à retirada, um movimento pode inverter duas, uma, ou mesmo nenhuma peça (se não houver peças vizinhas à que está sendo retirada). Você vence o jogo quando consegue remover todas as peças. A figura abaixo exemplifica uma sequência de movimentos que resolvem uma instância do problema com 5 peças, em que as peças são retiradas na ordem 5-2-1-3-4.

Para uma determinada disposição inicial das peças, podem existir várias soluções diferentes. Por exemplo, poderíamos retirar as peças na ordem 5-2-3-4-1 e ainda assim conseguir retirar todas as peças.

Sua tarefa, neste problema, consiste em contar o número de soluções diferentes para uma dada disposição inicial das peças. Como o número de soluções pode ser muito grande, você deve imprimir apenas o resto do número quando dividido por 10007.

Entrada

A primeira linha da entrada contém o inteiro N. A linha seguinte contém N letras separadas por espaço representando o arranjo inicial das peças. Uma peça branca é indicada pela letra B na entrada, e uma peça preta é indicada pela letra P.

Saída

Seu programa deve imprimir uma linha contendo o número de soluções distintas que resolvem o jogo.

Restrições

• 1 ≤ N ≤ 1000.

Exemplos

Entrada
5
B P B P P

Saída
11

Entrada
3
B P B

Saída
2