問題文
1≤Ai≤Mを満たす長さNの非負整数列A全てにおいて
max(A)+min(A)の値の和をmod109+7 で求めなさい。
制約
- 1≤N≤109
- 1≤M≤109
入力
入力はすべて整数である
出力
計算結果を一行に出力せよ
サンプル
入力例1
出力例1
これを満たす数列Aは (1,1),(1,2),(2,1),(2,2) の4通りあります
よって (1+1)+(2+1)+(2+1)+(2+2)=12 を出力します
入力例2
出力例2
入力例3
出力例3
mod109+7 で出力することを忘れないでください
入力例4
出力例4