Візерунок Дракона
Крива дракона — це ламана лінія, що складається з відрізків довжини 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.