Descrizione del percorso
Si considera una griglia di dimensioni
n x n. Un percorso inizia dalla cella (1, 1), passa per tutte le celle e termina nella cella (n, 1). Il percorso può muoversi solo verso destra (R), sinistra (L), sopra (U) o sotto (D), e ogni cella può essere visitata al massimo una volta. Questo percorso viene descritto utilizzando i caratteri LRUD, dove ciascun carattere rappresenta un movimento nella direzione corrispondente.
Tuttavia, alcuni caratteri della descrizione del percorso sono sostituiti con punti interrogativi (?), indicando che non si conosce la direzione esatta.L’obiettivo è determinare il numero di percorsi differenti che corrispondono alla descrizione fornita.
Ingresso
La prima riga contiene un singolo intero
n (3 ≤ n ≤ 6), che rappresenta la dimensione della griglia.
La seconda riga contiene la descrizione del percorso, ovvero una stringa di caratteri composta da L, R, U, D e ?, dove ciascun carattere indica uno spostamento nella direzione indicata. La lunghezza della descrizione del percorso è .Uscita
Stampare un singolo intero, che rappresenta il numero di percorsi differenti che soddisfano la descrizione data.
Esempi
Ingresso | Uscita |
3
RR??LUL? | 1 |
4
??R??????????L? | 3 |
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB