题目描述

在一个风狂雨骤的无限大的二维平面内，每一个 $1\times 1$ 的方格上都有概率落雨。具体地，记当前格子的落雨概率为 $p$，在 $1$ 时刻时 $p=\frac 1k$。

在每个时刻的结束时，有 $p$ 的概率落雨，此时 $p$ 重置为 $\frac 1k$；另外 $1-p$ 的概率不落雨，此时 $p\leftarrow p+\frac 1k$。显然，每一个格子至多间隔 $k$ 秒落一次雨滴。

现在 Einniw 身在 $(0,0)$，他想要避雨逃回家中。他从 $l$ 时刻开始，预计在 $r$ 时刻逃到家。

期间他的行动轨迹可以用一串长度为 $r-l$ 的仅包含 LRUD 的字符串描述，其中 LRUD 分别表示他在这一时刻往左/右/上/下花一个时刻的时间跑一格。

我们称 Einniw 淋到雨当且仅当存在一个时刻 $t\in [l,r]$ 结束时，Einniw 所在的格子有雨滴落下。注意 Einniw 出发以及到家的时刻也可以淋到雨。

Einniw 现在不想淋雨。请你告诉他不淋到雨的概率，对 $998244353$ 取模。

输入格式

共 $2$ 行。

第一行三个正整数 $k,l,r$，表示落雨常数，出发时刻，到家时刻。

第二行一个字符串 $S$，表示 Einniw 的行动轨迹。

输出格式

一行一个整数，表示淋雨概率。

具体地，设淋雨概率为 $p=\frac ab$，那么请输出 $a\times b^{-1} \bmod 998244353$ 的值。

样例一

input

2 1 6
LDRUD

output

995502593

样例二

input

7 10 20
UUUUUURDLU

output

665205887

样例三

见下发文件 $\texttt{ex\_rain3.in/ans}$。

样例四

见下发文件 $\texttt{ex\_rain4.in/ans}$。

限制与约定

对于所有数据，$1\le k\le 20, 1\le lLRUD。

时间限制： $1\texttt{s}$

空间限制： $512 \texttt{MiB}$