SPY2 - Spy

no tags 

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 NL 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 106. 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 109 +2015. (Why not 109+7? Remember Blue Mary is a weird girl!)

Example

Input:
2 2

Output:
3

hide comments
Francky: 2016-07-09 12:31:05

Really nice problem ; solved in mountain camp ; solution send from Mt Blanc.
Many thanks for this task.

edit : I thought test cases would be mainly bigger. My solution is optimized for biggest input.

Last edit: 2016-07-09 12:36:54

Added by:Fudan University Problem Setters
Date:2012-11-21
Time limit:33s
Source limit:3333B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:Based on a Problem from NEERC Western Subregional Contest 201X