aab aba baa (Hard version)

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

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

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

答えを行に出力せよ．

2 2
baab

4

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

30 30
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

589253743

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaはaが個， が個使われている文字列全体のうち，辞書順で番目です． よってこれをで割った余りであるを出力します．