Under construction

Still being built. Things may change

Sum of Powers 1

Time limit1sMemory limit512 MB

Summary
Given n and p, compute the sum of k^p for k from 1 to n, modulo 10^9+7, where n is up to 1e9 and p is up to 1000.
Level

Medium6 of 10

Topics
Math, Number theory
Solved
No attempts yet

Problem

Find the sum of the pp-th powers of all natural numbers from 1 to nn, modulo 109+710^9+7. In other words, compute the following value.

(∑k=1nkp) mod (109+7)\left(\sum_{k=1}^{n}k^p\right)\bmod\left(10^9+7\right)

Input

The first line contains nn and pp, separated by a space.

Output

Print the sum of the powers modulo 109+710^9+7.

Constraints

  • 1≤n≤1091\leq n\leq 10^9
  • 0≤p≤10000\leq p\leq 1000

Examples3

  1. Example 1

    Input
    5 3
    Expected output
    225

  2. Example 2

    Input
    7 0
    Expected output
    7

  3. Example 3

    Input
    1000000000 1
    Expected output
    21