黑暗爆炸OJ

DARKBZOJ

#4126. 国王奇遇记加强版之再加强版

统计下载数据

Description

同原题，见OJ3516

但本题中m<=500000

Input

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

Output

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

Sample Input

5 3

Sample Output

36363

Hint

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

Source

By wjy1998