3157 - 国王奇遇记

Input

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

Output

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

Examples

Input


5 3

Output

36363

Hint

1<=N<=10^9,1<=M<=200

时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题