Vira!

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.

1 2 3 4 5	Descrição do movimento
	Configuração inicial
	Removemos a peça da posição 5
	Removemos a peça da posição 2
	Removemos a peça da posição 1
	Removemos a peça da posição 3
	Removemos a peça da posição 4
	Fim do jogo.

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.

Informações sobre a pontuação

• Em um conjunto de casos de teste que totaliza 30 pontos, N ≤ 7.
• Em um conjunto de casos de teste totalizando 60 pontos, N ≤ 1000.

Exemplos

5
B P B P P
			

15
			

3
B P B
			

2