Nimultiset

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

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

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

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

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

• 入力はすべて整数

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

2 2

3

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

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

5 3

5301

1 1048576

0

12 345678

783055785

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