aab aba baa (Hard version)

2 secs 1024 MB
RedSpica's icon RedSpica

問題文

aAA個,bBB個からなる文字列SSが与えられます. aAA個,bBB個からなる文字列すべてのうち,SSは辞書順で何番目ですか. 答えは非常に大きくなる場合があるので,998244353998244353で割ったあまりを求めてください.

制約

  • 1A,B1031 \leq A,B \leq 10^3
  • S=A+B|S|=A+B
  • SSは英小文字aまたはbからなる

入力

入力は以下の形式で標準入力から与えられます.

AABB
SS

出力

答えを11行に出力せよ.

サンプル

入力1
2 2
baab
出力1
4

22個のa22個のbからなる文字列を辞書順に並べると aabb,abab,abba,baab,baba,bbaa となります.よってbaabは辞書順で44番目であるので44を出力します.

入力2
30 30
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
出力2
589253743

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa3030個, BB3030個使われている文字列全体のうち,辞書順で118264581564861424118264581564861424番目です. よってこれを998244353998244353で割った余りである589253743589253743を出力します.

Submit


Go (1.21)