#1566. [NOI2009] 管道取珠

[NOI2009] 管道取珠

题目描述

管道取珠是小 X 很喜欢的一款游戏。在本题中,我们将考虑该游戏的一个简单改版。游戏画面如图 1 所示:

游戏初始时,左侧上下两个管道分别有一定数量的小球(有深色球和浅色球两种类型),而右侧输出管道为空。每一次操作,可以从左侧选择一个管道,并将该管道中最右侧的球推入右边输出管道。

例如:我们首先从下管道中移一个球到输出管道中,将得到图 2 所示的情况。

假设上管道中有 nn 个球, 下管道中有 mm 个球,则整个游戏过程需要进行 n+mn+m 次操作,即将所有左侧管道中的球移入输出管道。最终 n+mn+m 个球在输出管道中从右到左形成输出序列。

爱好数学的小 X 知道,他共有 (n+mm)\binom{n+m}{m} 种不同的操作方式,而不同的操作方式可能导致相同的输出序列。举个例子,对于图 3 所示的游戏情形:

我们用 A 表示浅色球,B 表示深色球。并设移动上管道右侧球的操作为 U,移动下管道右侧球的操作为 D,则共有 (2+11)=3\binom{2+1}{1}=3 种不同的操作方式,分别为 UUD,UDU,DUU;最终在输出管道中形成的输出序列(从右到左)分别为 BAB,BBA,BBA。可以发现后两种操作方式将得到同样的输出序列。

假设最终可能产生的不同种类的输出序列共有 KK 种,其中:第 ii 种输出序列的产生方式(即不同的操作方式数目)有 aia_i 个。聪明的小 X 早已知道,

ai=(n+mm)\sum a_i=\binom{n+m}{m}

因此,小 X 希望计算得到:

ai2\sum a_i^2

你能帮助他计算这个值么?由于这个值可能很大,因此只需要输出该值对 10245231024523 取模后的结果。

输入格式

输入文件中的第一行为两个整数 n,mn,m,分别表示上下两个管道中球的数目。

第二行中为一个长度为 nn 的字符串,表示上管道中从左到右球的类型。其中:A 表示浅色球,B 表示深色球。

第三行中为一个长度为 mm 的字符串,表示下管道中从左到右球的类型。

保证两个字符串都只包含 A,B 两个字母。

输出格式

输出一个整数,即为 ai2\sum a_i^210245231024523 取模的结果。

样例 #1

样例输入 #1

2 1
AB
B

样例输出 #1

5

样例解释 #1

样例对应图 3。

共有两种不同的输出序列形式,序列 BAB 有 11 种产生方式,而序列 BBA 有 22 种产生方式,因此答案为 55

数据范围

  • 对于 30%30\% 的数据,满足 m,n12m,n \leq 12
  • 对于 100%100\% 的数据,满足 1m,n5001 \leq m,n \leq 500