F. Новый год и уборка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Лимак — белый медвежонок, которому родители сказали убраться в доме накануне Нового Года. Их дом можно представить как прямоугольную таблицу, состоящую из h рядов и w столбцов. Все клетки пустые, и по ним можно передвигаться.

Медвежонок маленький, и поэтому сам он не может убраться в доме. Вместо этого он собирается использовать робота-уборщика.

Робот-уборщик обладает встроенным шаблонов из n движений, определяемым строкой длины n. Одно движение (один символ) передвигает робота в одну из смежных клеток. Каждый символ является одним из следующих четырёх: 'U' (движение вверх), 'D' (движение вниз), 'L' (движение влево), 'R' (движение вправо). На каждое движение требуется ровно одна минута.

Лимак помещает робота-уборщика в некоторую клетку таблицы и влючает. После этого робот повторяет свой шаблон движений, пока не упрётся в стену (одну из четырех границ дома). Когда робот упрётся в стену, он выключается, после чего его можно снова поставить в какую-нибудь клетку и включить.

Лимак не уверен, будет ли достаточно поместить робота-уборщика в одной клетке, поэтому собирается запускать робота h·w раз, по одному разу из каждой клетки. Вполне может оказаться, что какие-то клетки были почищены более одного раза, но кому какое дело?

Лимак хочет знать, сколько времени уйдёт на уборку по такому алгоритму. Посчитайте необходимое количество минут по модулю 109 + 7. Также возможно, что робот-уборщик никогда не остановится, тогда выведите "-1" (без кавычек).

Считайте, что Лимак мгновенно ставит робота в нужную клетку и включает. Ход робота, на котором он упирается в стену, также занимает одну минуту и учитывается в ответе. Для уточнения посмотрите в комментарии к примерам.

Входные данные

В первой строке входных данных записано три целых числа n, h и w (1 ≤ n, w, h ≤ 500 000) — длина встроенного шаблона, количество строк и столбцов в таблице, соответственно.

Во второй строке записана строка длины n — шаблон движения из n ходов. Каждый символ — одна из следующих заглавных букв: 'U', 'D', 'L', 'R'.

Выходные данные

Выведите единственную строку с ответом.

Если робот никогда не закончит уборку, то выведите "-1" (без кавычек). В противном случае выведите продолжительность уборки по модулю 109 + 7.

Примеры
Входные данные
1 10 2
R
Выходные данные
30
Входные данные
3 4 6
RUL
Выходные данные
134
Входные данные
4 1 500000
RLRL
Выходные данные
-1
Примечание

В первом примере дом представляется табличкой из 10 строк и 2 столбцов. Если запустить робота в какой-либо клетке второго столбца, то он совершит ровно один ход (потратит на это одну минуту), в котором он ударится о стену, поскольку попробует пойти направо, но третьего столбца нет. Соответственно, начиная в первом столбце, робот сделает два хода. Итоговая продолжительность уборки составляет 10·1 + 10·2 = 30.

Во втором примере робот будет пытаться выполнять последовательность "RULRULRULR...". Например, если запустить его в самой левой клетке второго ряда, то он совершит ровно пять ходов, перед тем как остановится, потому что ударится в стену.