Description

本题中m<=500000

Format

Input

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

Output

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

Samples

5 3

36363

Limitation

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