Limak 是一只小北极熊。他的父母让他在除夕之前打扫房子。他们的房子是一个长方形网格,有 h 行和 w 列。每个单元格都是一个空的正方形。
他是一只小熊,因此他不能自己打扫房子。相反,他将使用清洁机器人。
清洁机器人有一个内置的 n 个动作模式,由长度为 n 的字符串定义。单次移动(角色)即可将机器人移动到四个相邻单元之一。每个字符都是以下四个字符之一:“U”(上)、“D”(下)、“L”(左)、“R”(右)。一个动作需要一分钟。
必须在某个单元格中放置并启动清洁机器人。然后它重复其移动模式,直到撞到墙壁(房子的四个边界之一)。撞到墙上后可以放置并再次使用。
Limak 不确定将清洁机器人放在一个牢房中是否足够。因此,他将启动它 w·h 次,每个牢房一次。也许有些细胞会被多次清洁,但谁在乎呢?
Limak 问你一个问题。打扫房子需要多长时间?查找并打印以 109 + 7 为模的分钟数。也有可能清洁机器人永远不会停止,然后打印“-1”(不带引号)。
放置和启动机器人不需要时间,但是,当机器人撞到墙壁时,您必须计算一次移动。查看示例以进一步说明。
输入
第一行包含三个整数 n、h 和 w (1 ≤ n, h, w ≤ 500 000) - 分别是模式的长度、行数和列数。
第二行包含长度为 n 的字符串 — n 个动作的模式。每个字符都是大写字母“U”、“D”、“L”或“R”之一。
输出
打印一行答案。
如果清洁机器人永远不会停止,请打印“-1”(不带引号)。否则,打印清洁房屋所需的分钟数模 109 + 7。
示例
输入 #1
1 10 2 R
输出 #1
30
输入 #2
3 4 6 RUL
输出 #2
134
输入 #3
4 1 500000 RLRL
输出 #3
-1
注意
第一个样板房是一个 10 行 2 列的网格。在第二列的任何位置启动机器人只会导致一次移动(因此,清洁一分钟),其中机器人会撞到墙上 - 他试图向右走,但没有第三列。在第一列的任意位置启动机器人将导致两次移动。总分钟数为 10·1 + 10·2 = 30。
在第二个示例中,启动的机器人将尝试移动“RULRULRULR...”例如,对于第二排最左边的单元,机器人将进行 5 次移动,然后由于撞到上墙而停止。