Cho N, k, tính (1^k + 2^k + …. + N ^k) mod 1000000007. Giới hạn 1 <= N <= 10^9, 1 <= k <= 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

Ví dụ:

Input
1 1
4 2

Output
1
30