Power Sum

Time limit2sMemory limit128 MB

Summary
Compute 1^K + 2^K + ... + N^K modulo 1,000,000,007 for N up to 10^9 and K up to 50.
Level

Medium7 of 10

Topics
Math, Combinatorics, Number theory
Solved
No attempts yet

Problem

Given positive integers N and K, compute the following value modulo 1,000,000,007.

1^K + 2^K + 3^K + ... + N^K

Input

The first line contains two positive integers, N and K. N is at most 10^9, and K is at most 50.

Output

Print the remainder of 1^K + 2^K + 3^K + ... + N^K divided by 1,000,000,007.

Examples4

  1. Example 1

    Input
    4 2
    Expected output
    30

  2. Example 2

    Input
    5 1
    Expected output
    15

  3. Example 3

    Input
    13 5
    Expected output
    1002001

  4. Example 4

    Input
    123456789 1
    Expected output
    383478132