The dragon curve is a polygonal chain with segments of length \textbf{1}, defined recursively. We choose some point on the plane and one of four directions, collinear to the coordinate axes. The left(right) dragon of order n is constructed in the following way: \begin{itemize} \item if \textbf{n} is equal to \textbf{0}, we construct a segment of length \textbf{1} from the current point in the current direction, moving to endpoint; \item otherwise we construct the left dragon of order \textbf{n−1} from the current point in the current direction, turn \textbf{90}degrees to the left(right) in the endpoint, and construct the right dragon of order \textbf{n−1}; \end{itemize} Let us construct the left dragon of order \textbf{n}, starting from the origin (point (\textbf{0}, \textbf{0})) in the positive direction of the axis \textbf{OX}. Given some pattern as a sequence of directions, in which sequential movements by unit length is performed, your task is to determine how many times does the given pattern occurs in the constructed dragon curve. \InputFile Input file contains integer \textbf{n} (\textbf{0} ≤ \textbf{n} ≤ \textbf{10^9}) and string \textbf{S} consisting of symbols \textbf{R}, \textbf{L}, \textbf{U} and \textbf{D}, which defines the pattern. \textbf{R} denotes rightward movement (positive direction of the axis \textbf{OX}), \textbf{L} denotes leftward movement (negative direction of the axis \textbf{OX}), \textbf{U} denotes upward movement (positive direction of the axis \textbf{OY}), \textbf{D} denotes downward movement (negative direction of the axis \textbf{OY}). The length of the string \textbf{S} is in the range from \textbf{1} to \textbf{10^6}. \OutputFile Output number of given patterns in the left dragon of the order \textbf{n}, constructed in the positive direction of an axis \textbf{OX}, modulo \textbf{10^9+7}.