国王奇遇记加强版

时间限制:1s      空间限制:128MB

题目描述

同原题,见Oj3157

但本题中m<=1000


输入格式

共一行包括两个正整数NM


输出格式

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


样例输入

5 3

样例输出

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

提示

没有写明提示


题目来源

By Lz