eolymp
bolt
Try our new interface for solving problems
Problems

Dragon Pattern

Dragon Pattern

Time limit 0.5 seconds
Memory limit 256 MiB

The dragon curve is a polygonal chain with segments of length 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:

  • if n is equal to 0, we construct a segment of length 1 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 90degrees to the left(right) in the endpoint, and construct the right dragon of order n−1;

Let us construct the left dragon of order n, starting from the origin (point (0, 0)) in the positive direction of the axis 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.

Input data

Input file contains integer n (0n10^9) and string S consisting of symbols R, L, U and D, which defines the pattern. R denotes rightward movement (positive direction of the axis OX), L denotes leftward movement (negative direction of the axis OX), U denotes upward movement (positive direction of the axis OY), D denotes downward movement (negative direction of the axis OY). The length of the string S is in the range from 1 to 10^6.

Output data

Output number of given patterns in the left dragon of the order n, constructed in the positive direction of an axis OX, modulo 10^9+7.

Examples

Input example #1
2 RU
Output example #1
1
Source ACM SEERC 2013, SouthEastern European Region, October, 12/10/2013, Vinnica & Bucharest