龙形曲线（dragon curve）是由长度为 1 的线段组成的折线，通过递归方式定义。我们在平面上选择某个点以及与坐标轴平行的四个方向之一。阶数为 $n$ 的左（右）龙形曲线按以下方式构建：

• 如果 $n$ 等于 0，我们从当前点出发，沿当前方向构建一条长度为 1 的线段，移动到终点；
• 否则，我们先从当前点出发，沿当前方向构建阶数为 $n-1$ 的左龙形曲线，在终点处向左（右）旋转 90 度，然后构建阶数为 $n-1$ 的右龙形曲线；

让我们从原点（点 $(0,0)$）出发，沿 $OX$ 轴的正方向构建阶数为 $n$ 的左龙形曲线。

给定一个表示为方向序列的模式，该序列代表连续的单位长度移动。你的任务是确定给定的模式在构建的龙形曲线中出现了多少次。

输入格式

输入包含一个整数 $n$（$0 \le n \le 10^9$）和一个由字符 R、L、U、D 组成的字符串 $S$，用于定义模式。其中：

• R 表示向右移动（$OX$ 轴的正方向）；
• L 表示向左移动（$OX$ 轴的负方向）；
• U 表示向上移动（$OY$ 轴的正方向）；
• D 表示向下移动（$OY$ 轴的负方向）。

字符串 $S$ 的长度在 $1$ 到 $10^6$ 之间。

输出格式

输出在沿 $OX$ 轴正方向构建的阶数为 $n$ 的左龙形曲线中，给定模式出现的次数，结果对 $10^9+7$ 取模。

样例

输入样例 1

2 RU

输出样例 1

1

输入样例 2

3 L

输出样例 2

3

输入样例 3

4 LDL

输出样例 3

2