問題文


個の整数からなる多重集合 があります。 の各要素は 以上 未満の整数です。

を使って Alice と Bob がゲームをします。Alice から始めて 人は交互に以下の操作を繰り返します。

  • 以上の整数が書かれた要素を つ選ぶ。選んだ要素の値が のとき、その要素を 以上 未満の整数に置き換える。

先に操作ができなくなったプレイヤーが負けで、負けなかったプレイヤーが勝ちです。

として考えられる全ての多重集合のうち、Bob がどのような操作をしても Alice が必ず勝てる多重集合の種類数を で割った余りで求めて下さい。

制約


  • 入力はすべて整数

入力


出力


行に答えを出力してください。

サンプル


入力1
2 2
出力1
3

として 種類が考えられます。

このうち Alice が必ず勝てるものは 種類です。

入力2
5 3
出力2
5301
入力3
1 1048576
出力3
0
入力4
12 345678
出力4
783055785

で割った余りで出力することに注意してください。

Submit


Go (1.14)