Dragon Pattern#6175
The dragon curve is a polygonal chain with segments of length , 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 is constructed in the following way:
if is equal to , we construct a segment of length from the current point in the current direction, moving to endpoint;
otherwise we construct the left dragon of order n-1 from the current point in the current direction, turn degrees to the left(right) in the endpoint, and construct the right dragon of order n-1;
Let us construct the left dragon of order , starting from the origin (point ) in the positive direction of the axis .
Given some pattern as a sequence of directions, in which sequential movements by unit length are performed, your task is to determine how many times does the given pattern occur in the constructed dragon curve.
Input file contains integer (0 \le n \le 10^9) and string consisting of symbols R, L, U and D, which defines the pattern. R denotes rightward movement (positive direction of the axis ), L denotes leftward movement (negative direction of the axis ), U denotes upward movement (positive direction of the axis ), D denotes downward movement (negative direction of the axis ). The length of the string is in the range from to 10^6.
Output number of given patterns in the left dragon of the order , constructed in the positive direction of an axis , modulo 10^9+7.
Example 1