Hay 88418 caminos en una cuadrícula de 7 por 7 desde el cuadrado superior izquierdo hasta el cuadrado inferior izquierdo. Cada camino corresponde a una descripción de 48 caracteres formada por los caracteres ~D (abajo), U (arriba), L (izquierda)~ y ~R (derecha)~.

Por ejemplo, la trayectoria

corresponde a la descripción ~DRURRRRRDDDLUULDDDLDRRURDDLLLLLURULURRUULDLLDDDD~.

Se le da una descripción de un camino que también puede contener caracteres ~?~ (cualquier dirección). Su tarea consiste en calcular el número de caminos que coinciden con la descripción.

Entrada

La única línea de entrada tiene una cadena de 48 caracteres ~?, D, U, L~ y ~R~.

Salida

Imprime un número entero: el número total de caminos.

Ejemplo de Entrada

??????R??????U??????????????????????????LD????D?

Ejemplo de Salida

201