Dragon Pattern

The dragon curve is a polygonal chain built from segments of length 1, defined recursively. Choose a point in the plane and one of the four directions parallel to the coordinate axes. The left (right) dragon of order $n$ is drawn like this:

• if $n$ is 0, draw a segment of length 1 from the current point in the current direction and move to its endpoint;
• otherwise draw the left dragon of order $n-1$ from the current point in the current direction, turn 90 degrees to the left (right) at the endpoint, then draw the right dragon of order $n-1$.

Draw the left dragon of order $n$ starting at the origin $(0, 0)$ in the positive direction of the axis $OX$. It makes $2^n$ moves of length 1 one after another, so writing down the direction of each move in order gives a string of length $2^n$.

A pattern is also a string of move directions. Count the substrings of that direction string that equal the pattern, that is, the number of positions where the pattern starts.

One line contains an integer $n$ and a string $S$ describing the pattern, separated by one space. $S$ consists only of the letters R, L, U, D. R means a move to the right (positive direction of the axis $OX$), L a move to the left (negative direction of $OX$), U a move up (positive direction of the axis $OY$), and D a move down (negative direction of $OY$).

$0 \le n \le 10^9$ and $1 \le |S| \le 10^6$.

Print how many times the pattern $S$ occurs in the left dragon of order $n$ drawn in the positive direction of the axis $OX$, modulo $10^9+7$.