时光飞逝，日子一天天过去，游戏终于结束了。Rikka 在你的帮助下从未喝过酒，所以她依然是一位名誉良好的日本公民。

红白优雅地离开了。突然，Rikka 意识到白方玩家是 LCR 而不是任何长者——或者说 LCR 就是那个人。她永远不会知道为什么她没能理解这一点。Rikka 追了上去，但在穿过迷雾时迷了路。

宇宙飞船在天空中进行着史诗般的航行，一排排道路和建筑物形成了同心圆，让人想起祭坛或八卦。在迷雾的尽头，一幅神圣而不可思议的景象出现在她面前。那颗巨大的圆形行星很快吸引了她——地球，人类的家园，像一块巨大的月饼一样悬挂着。多么壮观的月球大都市！

Rikka 发现自己站在证券交易所前。一个男孩正盯着屏幕，敲击着键盘，吸引了她的目光。

有两种类型的股票。它们都由财团控制，因此它们的趋势是既定的。

每种类型的股票都可以分为若干阶段，这些阶段将按顺序进行。一种类型有 $n$ 个阶段，另一种有 $m$ 个阶段。在每个阶段，人们会获得或损失一个单位的钱。男孩起初只有一个单位的钱，他每天必须处理一种任意类型的阶段（除非该类型的所有阶段都已处理完毕，如果是这样，则处理另一种类型）。在 $(n + m)$ 天后，所有交易结束，他最终将得到他的钱。

这个可怜的男孩什么都不知道，无法做出决定，所以他随机选择。然而，在无数次破产之后，他获得了一种敏锐的直觉：如果他只有一单位的钱，他就会知道所有可用阶段的结果。当且仅当他能立即选择某个阶段时，该阶段才是可用的。在这种情况下，除非所有可用的类型都会导致他亏钱，否则他永远不会选择会导致他亏钱的类型。但如果他至少有两单位的钱，他会忽略任何已知信息并随机选择，因为他有回旋余地。他必须每天进行处理，并且在所有交易完成之前不能退出，因为他只能在 $(n + m)$ 天后拿到现金。

每当他的钱用完时，他就会破产。如果他只有一单位的钱，并且每种可用类型（至少有一个阶段未处理）在接下来的阶段中都可能导致他亏钱，那么他就会破产。

当然，心地善良的女孩会尽力帮助他。她在之前得到的代码中发现了一些奇怪的东西。那是来自财团的文件的哈希值！

不久之后，Rikka 得到了两个长度分别为 $n$ 和 $m$ 的字符串。每个字符串包含三种类型的字符“P”、“V”和“？”，分别表示相应的阶段可能导致亏损、获利或未知。然而，男孩不相信她。

Rikka 很焦虑。她想知道，根据她的信息，有多少种可能的趋势永远不会导致他破产，结果对 998244353 取模。

一种可能的趋势可以用两个长度分别为 $n$ 和 $m$ 的仅包含“P”和“V”的字符串来描述，它们可以通过将 Rikka 字符串中的每个“？”替换为“P”或“V”来获得。当且仅当无论他每次如何选择，他都永远不会破产时，该趋势才永远不会导致破产。

输入格式

第一行包含一个长度为 $n$ 的字符串 $s$ ($1 \le n \le 5000$)，仅由“P”、“V”和“？”组成。 第二行包含一个长度为 $m$ 的字符串 $t$ ($1 \le m \le 5000$)，仅由“P”、“V”和“？”组成。 $s$ 和 $t$ 构成了 Rikka 的信息。

输出格式

输出一个整数，表示永远不会导致男孩破产的可能趋势数量，对 998244353 取模。

样例

输入 1

PV
??

输出 1

1

输入 2

???
P?P

输出 2

3

输入 3

?????
?????

输出 3

326

说明

在第一个样例中，有 4 种将“？”替换为“P”或“V”的方法，如下所示：

• “PV”和“PP”：男孩别无选择，只能在第一天输掉他所有的钱。
• “VV”：在第一天，由于男孩只有一单位的钱，为了避免破产，他会选择第二种类型，因此在第二天开始时，他手中有两单位的钱。他不可能破产，因为只剩下一个“P”。
• “VP”：在第一天，男孩只能选择第二种类型。但在第二天，两种类型都可以选择。如果他选择第二种类型，他将不得不在第三天选择第一种类型，然后他就会破产。

由于只有“VV”永远不会导致男孩破产，因此第一个样例的答案应该是 1。