Ebi-chan and Integer Sequences

Time Limit : 2 sec, Memory Limit : 262144 KB

B: えびちゃんと数列 - Ebi-chan and Integer Sequences -

問題

えびちゃんは数列が好きです。中でも等差数列が特に好きです。 今回は以下の条件を満たす数列を作ることにしました。

  • 長さ n の等差数列である
  • 数列の i 番目の要素を s_i と定める時、全ての s_i (1 \leq i \leq n)0 \leq s_i \leq m を満たす整数である

上の条件を満たすような数列はいくつあるでしょうか? ただし答えは非常に大きくなることがあるので、 10^9 + 7 で割った余りを出力してください。

入力形式

入力は一行で与えられる。

n m

n は数列の長さを表す。

制約

  • 1 \leq n \leq 10^{15}
  • 0 \leq m \leq 10^{15}

出力形式

条件を満たす等差数列の数を 10^9 + 7 で割った余りを一行に出力せよ。

入力例1

3 9

出力例1

50

入力例2

10000000000 10000000000

出力例2

999999942

入力は32bit整数には収まりきらないことに注意してください。

Note

Link
 
Source: Aizu Competitive Programming Camp 2017 Day3 , Japan, 2017-09-20