题目描述

同原题，见 P3157。

但本题中 $m \le 1000$。

输入格式

共一行包括两个正整数 $n$ 和 $m$。

输出格式

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

5 3

36363

HINT

$1 \le n \le 10^9,1 \le m \le 1000$

题目来源

By Lz