No.665 Bernoulli Bernoulli

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 39
作問者 : koba-e964koba-e964 / テスター : はむこはむこ
0 ProblemId : 1917 / 出題時の順位表

Note

writerの想定解的にLLだと厳しいかもしれません。

問題文

$1^k + \cdots + n^k$ modulo $10^9 + 7$を計算してください。

入力

$n$ $k$

$1 \le n \le 10^{16}$
$1 \le k \le 10^4$

出力

結果を1行に出力してください。最後に改行をしてください。

サンプル

サンプル1
入力
10 1
出力
55

$1 + 2 + \cdots + 10 = 55$です。

サンプル2
入力
10 3
出力
3025

$1^3 + 2^3 + \cdots + 10^3 = 3025$です。

サンプル3
入力
10000 10000
出力
379988108

サンプル4
入力
1234567890123456 10000
出力
837110143

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。