問題文


非負整数の集合 に対し、 を「 に含まれない最小の非負整数」として定義します。

以上 未満の整数からなる長さ の数列 として考えられるものは 通りありますが、この全てに対する次の操作を行った後の の総和を で割った余りを求めてください。

  1. まず、集合 を用意する。これは最初空である。また、整数 を用意する。これは最初それぞれ である。
  2. が含まれないなら、 を追加する。
  3. を加算し、 を加算する。
  4. もし なら操作を終了する。そうでなければ、操作2に戻る。

制約


  • 入力は全て整数

入力


N K

出力


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

サンプル


入力1
3 2
出力1
27

数列 としてありうるものは、 通りです。

回目の操作3で加算される数の総和はそれぞれ であるため、答えは となります。

入力1
900000000 100000
出力1
872760129

で割った余りを出力してください。

提出


Go (1.14)