Descrição do Caminho
É-lhe dada uma grelha (matriz) de tamanho
n x n. Um caminho começa na célula (1, 1), visita todas as células e termina na célula (n, 1). Esse caminho só pode avançar para a direita (R), esquerda (L), cima (U) ou baixo (D), e cada célula só pode ser visitada, no máximo, uma vez. O caminho é descrito usando os carateres LRUD, em que cada carater representa um movimento na direção correspondente.
No entanto, alguns carateres na descrição do caminho são substituídos por pontos de interrogação (?), indicando que a direção é desconhecida.A sua tarefa é encontrar o número de diferentes caminhos que correspondem à descrição dada.
Entrada
A primeira linha contém um único inteiro
n (3 ≤ n ≤ 6), que representa o tamanho da grelha.
A segunda linha contém a descrição do caminho, que é uma string composta pelos carateres L, R, U, D e ?, em que cada carater representa um movimento na direção correspondente. O comprimento da descrição do caminho é igual a .Saída
Imprima um único inteiro, representando o número de diferentes caminhos que correspondem à descrição dada.
Exemplos
Input | Output |
3
RR??LUL? | 1 |
4
??R??????????L? | 3 |
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB