Узор Дракона
Кривая дракона — это полигональная цепь с отрезками длины 1, которая определяется рекурсивно. Мы начинаем с некоторой точки на плоскости и выбираем одно из четырех направлений, совпадающих с координатными осями. Левый (правый) дракон порядка n строится следующим образом:
Если n равно 0, мы строим отрезок длины 1 от текущей точки в текущем направлении, перемещаясь к конечной точке;
В противном случае, мы строим левого дракона порядка n−1 от текущей точки в текущем направлении, затем поворачиваем на 90 градусов влево (вправо) в конечной точке и строим правого дракона порядка n−1;
Построим левого дракона порядка n, начиная из начала координат (точка (0, 0)) в положительном направлении оси OX.
Дан некоторый шаблон в виде последовательности направлений, в которых выполняется последовательное перемещение на единичную длину. Ваша задача — определить, сколько раз данный шаблон встречается в построенной кривой дракона.
Входные данные
Входной файл содержит целое число n (0 ≤ n ≤ 10^9) и строку S, состоящую из символов R, L, U и D, которые определяют шаблон. R обозначает движение вправо (положительное направление оси OX), L обозначает движение влево (отрицательное направление оси OX), U обозначает движение вверх (положительное направление оси OY), D обозначает движение вниз (отрицательное направление оси OY). Длина строки S находится в диапазоне от 1 до 10^6.
Выходные данные
Выведите количество данных шаблонов в левом драконе порядка n, построенном в положительном направлении оси OX, по модулю 10^9+7.