薇尔莉特的打字机

题目背景

> 只要客人有意向,不论身在何处,都能上门服务。我是自动手记人偶服务——薇尔莉特·伊芙加登。 ![](http://wx3.sinaimg.cn/large/dcec95dfgy1fme08p9eopj20xv0hyq5q.jpg)

题目描述

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

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

2 4
AB
AuAB

输出样例 #1

9

输入样例 #2

10 5
AABBAACBAC
ABAAC

输出样例 #2

20

输入样例 #3

1 3
U
uUu

输出样例 #3

3

说明

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