XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: vira.x, onde x deve ser c, cpp, java, js ou py

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.

12345
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

Entrada
5
B P B P P
			
Saída
15
			
Entrada
3
B P B
			
Saída
2
			

Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação