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

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

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

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

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

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

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