Cho ~N~, ~k~, tính ~(1^{k} + 2^{k} +~ ...~+ N^{k})~ mod ~1000000007~. Giới hạn ~1 \le N \le 10^{9}~, ~1 \le k \le 50~.

Input

Gồm nhiều dòng, mỗi dòng chứa 2 số ~N~, ~k~ là những bộ test của bài

Output

Ghi ra kết quả ứng với mỗi bộ test

Sample Input

1 1
4 2

Sample Output

1
30