Descripción del recorrido

Se tiene una cuadrícula de tamaño n x n. Un recorrido comienza en la celda (1, 1), visita todas las celdas y finaliza en la celda (n, 1). El recorrido solo puede desplazarse hacia la derecha (R), izquierda (L), arriba (U) o abajo (D), y no puede pasar más de una vez por cada celda. Para describir el recorrido, se utilizan los caracteres LRUD, donde cada uno representa un movimiento en la dirección correspondiente. No obstante, algunos caracteres en la descripción están reemplazados por signos de interrogación (?), lo que indica que la dirección no se conoce de antemano.

El objetivo es determinar cuántos recorridos distintos coinciden con la descripción proporcionada.

Entrada

La primera línea contiene un único entero n (3 ≤ n ≤ 6), que representa el tamaño de la cuadrícula. La segunda línea contiene la descripción del recorrido, es decir, una cadena de caracteres que puede incluir L, R, U, D y ?, donde cada carácter representa un movimiento en la dirección respectiva. La longitud de esta descripción es n^2 - 1.

Salida

Se debe imprimir un único número entero que represente la cantidad de diferentes recorridos que coinciden con la descripción dada.

Ejemplos