入力

入力は以下の形式で標準入力から与えられる。

N K

• 1 行目に、 2 個の整数 N, K (1 ≦ N, K ≦ 10⁹) がスペース区切りで与えられる。

部分点

この問題は AtCoder Beginner Contest の問題としては非常に難しいため、通常 (100 点満点) と異なり 101 点満点であり、部分点が設定されている。

• 5 点分のテストケースは 1 ≦ N, K ≦ 100 を満たす。
• 別の 10 点分のテストケースは 1 ≦ N ≦ 10⁴, 1 ≦ K ≦ 100 を満たす。
• さらに別の 85 点分のテストケースは 1 ≦ N ≦ 10⁹, 1 ≦ K ≦ 100 を満たす。以上で合計 100 点となる。

出力

標準出力に、求める和を 1,000,000,007 で割った余りを出力せよ。

末尾の改行を忘れないこと。