Path Description

You are given an n x n grid of cells. A path starts from the cell (1, 1), visits all the cells, and ends at the cell (n, 1). The path can only move right (R), left (L), up (U), or down (D), and it can visit each cell at most once. The path is described using the characters LRUD, where each character represents a movement in the corresponding direction. However, some characters in the path description are replaced with question marks (?), indicating that the direction is unknown.
Your task is to find the number of different paths that match the given path description.

Input

The first line contains a single integer n (3 ≀ n ≀ 6), representing the size of the grid. The second line contains the path description, which is a string of characters consisting of L, R, U, D, and ?, where each character represents a movement in the corresponding direction. The length of the path description is equal to .

Output

Print a single integer, representing the number of different paths that match the given path description.

Examples

Input
Output
3 RR??LUL?
1
4 ??R??????????L?
3

Constraints

Time limit: 3 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue