aab aba baa (Hard version)

2 secs 1024 MB
RedSpica

問題文


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

制約


  • は英小文字aまたはbからなる

入力


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


出力


答えを行に出力せよ.

サンプル


入力1
2 2
baab
出力1
4

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

入力2
30 30
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
出力2
589253743

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

提出


Go (1.14)