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