#1516. 国王奇遇记加强版

国王奇遇记加强版

Description

同原题,见Oj3157

但本题中m<=1000

Format

Input

共一行包括两个正整数N和M。

Output

共一行为所求表达式的值对10^9+7取模的值。

Samples

5 3
36363
HINT
1<=N<=10^9,1<=M<=1000

Limitation