불멸의 우주

시간은 빠르게 흐른다. 며칠이 지나고 게임이 마침내 끝났다. 릭카는 당신의 도움을 받아 술을 마신 적이 없으므로, 여전히 평판 좋은 일본 시민이다.

빨간 쪽과 하얀 쪽이 우아하게 떠났다. 그때 갑자기 릭카는 하얀 쪽이 어떤 장로가 아니라 LCR이라는 것을 깨닫는다. 아니, 정확히는 LCR이 바로 그 사람이다. 그녀는 왜 그것을 알아채지 못했는지 끝내 알지 못한다. 릭카는 두 사람을 쫓아갔지만, 안개를 지나는 동안 길을 잃는다.

우주선들이 하늘을 가로지르며 장대한 항해를 이어 가고 있다. 도로와 건물이 동심원을 이루며 줄지어 있어, 사람들에게 제단이나 팔괘를 떠올리게 한다. 안개가 걷히자 눈앞에 장엄한 풍경이 펼쳐진다. 거대한 둥근 행성, 인류의 고향인 지구가 커다란 월병처럼 걸려 있다. 달 위의 대도시가 이토록 웅장하다니!

릭카는 어느새 증권거래소 앞에 서 있다. 화면을 응시하며 키보드를 두드리는 소년이 그녀의 눈에 들어온다.

주식에는 두 종류가 있다. 둘 다 기업 연합이 운영하므로 그 흐름은 이미 정해져 있다.

각 종류의 주식은 여러 단계로 나뉘며, 단계는 순서대로 처리된다. 한 종류는 $n$단계이고 다른 종류는 $m$단계다. 각 단계에서는 돈을 한 단위 얻거나 잃는다. 소년은 처음에 돈을 한 단위 가지고 있다. 그는 매일 아무 종류에서나 단계 하나를 처리해야 한다. 다만 어느 종류의 단계가 모두 처리되었다면 나머지 종류를 처리한다. $(n + m)$일이 지나면 모든 거래가 끝나고, 그는 마침내 돈을 받는다.

이 가난한 소년은 판단에 도움이 될 정보를 아무것도 모르므로 무작위로 고른다. 그러나 그에게는 날카로운 직감이 있다. 돈이 한 단위뿐일 때, 그는 선택 가능한 모든 단계의 결과를 알 수 있다. 단계가 선택 가능하다는 것은 곧바로 고를 수 있다는 뜻이다. 이때 그는 모든 선택 가능한 종류가 돈을 잃게 만들 때가 아니라면, 돈을 잃게 만드는 종류를 고르지 않는다. 하지만 돈이 두 단위 이상이면, 아는 정보를 무시하고 무작위로 고른다. 기회가 있기 때문이다. 그는 매일 단계를 하나씩 처리해야 하고, 현금은 $(n + m)$일 후에야 받을 수 있으므로 모든 거래가 끝나기 전에 떠날 수 없다.

돈이 떨어지면 그는 파산한다. 돈이 한 단위뿐이고, 처리되지 않은 단계가 남아 있는 선택 가능한 종류가 모두 다음 단계에서 그 돈을 잃게 만드는 경우에 파산이 일어난다.

물론 마음씨 고운 소녀는 최선을 다해 돕고자 한다. 그녀는 전에 받은 코드에서 이상한 것을 발견한다. 기업 연합 파일의 해시 값이었다!

얼마 지나지 않아 릭카는 길이가 각각 $n$과 $m$인 두 문자열을 받는다. 각 문자열은 'P', 'V', '?'만으로 이루어져 있으며, 해당 단계가 손실, 이익, 또는 알 수 없음을 뜻한다. 그러나 소년은 그녀의 말을 믿지 않는다.

릭카는 불안해진다. 그녀가 가진 정보에 따르면, 소년을 파산시키지 않을 가능한 흐름이 몇 가지인지 $998244353$으로 나눈 나머지로 알고 싶어 한다.

가능한 흐름은 릭카의 두 문자열에서 각 '?'를 'P' 또는 'V'로 바꿔 얻은, 'P'와 'V'로만 이루어진 길이 $n$과 $m$인 두 문자열로 나타낸다. 흐름은 소년이 매번 어떻게 고르든 파산하지 않을 때, 그리고 그때에만 파산하지 않는다.

첫 줄에는 길이가 $n$ ($1\le n \le 5000$)인 문자열 $s$가 주어진다. 문자열은 'P', 'V', '?'로만 이루어져 있다.

둘째 줄에는 길이가 $m$ ($1\le m \le 5000$)인 문자열 $t$가 주어진다. 문자열은 'P', 'V', '?'로만 이루어져 있다.

$s$와 $t$가 릭카의 정보를 이룬다.

소년을 파산시키지 않는 가능한 흐름의 수를 한 개의 정수로 출력한다. 답은 $998244353$으로 나눈 나머지다.

첫 번째 예제에서는 '?'를 'P' 또는 'V'로 바꾸는 방법이 4가지 있다. 다음과 같다.

• PV와 PP: 소년은 첫날 가진 돈을 모두 잃는 수밖에 없다.
• VV: 첫날 소년은 돈이 한 단위뿐이므로 파산을 피하려고 두 번째 종류를 고른다. 그래서 둘째 날을 시작할 때 두 단위를 가진다. 'P'가 하나만 남아 있으므로 파산할 수 없다.
• VP: 첫날 소년은 두 번째 종류만 고를 수 있다. 둘째 날에는 두 종류 모두 고를 수 있다. 두 번째 종류를 고르면 셋째 날에는 첫 번째 종류를 고를 수밖에 없고, 그러면 파산한다.

소년을 파산시키지 않는 경우는 VV 하나뿐이므로, 첫 번째 예제의 답은 1이다.