薇尔莉特的打字机

> 只要客人有意向，不论身在何处，都能上门服务。我是自动手记人偶服务——薇尔莉特·伊芙加登。 

薇尔莉特的打字机用了太久，按键已经开始老化了，因此有时候按键会没有反应。而薇尔莉特总是盲打，因此按键没反应她也不会注意到。一天，她用这台打字机继续完成一封还没写完的信。 现在告诉你这封信已经写好的部分以及薇尔莉特想进行的操作，薇尔莉特想进行的操作有两种： 1. 在信的末尾输入一个大写字母 2. 进行一次退格 退格用小写字母 $\mathrm{u}$ 表示，即删除当前信中的最后一个字符，当然，在信为空时退格没有任何作用。 薇尔莉特会按顺序按下她想按的按键，而每次薇尔莉特按下一个键（输入一个大写字母或进行一次退格），都有可能没有反应（即这次操作无效）。请问，最后打出来的信有多少种可能呢？（空信也算信） 当然薇尔莉特只想知道可能数对 `0x125E591`（十六进制） 取模的结果。

第一行两个正整数 $n,\ m$ 分别表示已经写好的信的长度和薇尔莉特想进行的操作数（字符个数+退格个数）。 第二行一个长度为 $n$ 的字符串表示已经写好的信，保证该串中的每个字符都为大写字母。 第三行一个长度为 $m$ 的字符串表示薇尔莉特想进行的操作，保证该串中的每个字符都为大写字母或 $\mathrm{u}$。

一个整数表示答案对 `0x125E591` 取模的结果。

2 4
AB
AuAB

9

10 5
AABBAACBAC
ABAAC

20

1 3
U
uUu

3

$1\le n,\ m\le 5\times 10^6$ ## 样例解释 样例一：可能的 $9$ 种信为：`A`,`AA`,`AB`,`AAB`,`ABA`,`ABB`,`ABAA`,`ABAB`,`ABAAB`。 样例二：~~太多了，略~~。 样例三：可能的 $3$ 种信为：`空`,`U`,`UU`。