Blue Mary extremely likes making PPTs. She has already made L PPTs. Now the only problem before finish is to set the background pictures for each PPT. She has N background pictures, and each PPT needs exactly one background picture. Different PPTs can use same background pictures. Obviously, there are N^L combinations.

For each combination, Blue Mary defines its weight as (k+1)^-1, where k is the number of pictures (from the N pictures in total) that do not appear in it. Now Blue Mary wants to calculate the sum of weights of all combinations. (Blue Mary is such a weird girl that she always does some meaningless calculations.) She asks you for help.

Input

Multiple test cases, the number of them is less than 500. Each test case consists of a single line with two space-separated integers N and L. All input numbers are positive and less than 10⁶. Input terminates by EOF.

Input data is almost log-uniform randomly generated.

Output

For each test case, output the required value in a single line. It's guaranteed that this number is always an integer for all input data. Since it can be quite large, output it modulo 10⁹ +2015. (Why not 10⁹+7? Remember Blue Mary is a weird girl!)

Example

Input:
2 2
Output:
3