Làm việc nhóm (lũy thừa k)

Bạn có một nhóm gồm $N$ người. Với một nhiệm vụ cụ thể, bạn có thể chọn bất kỳ tập con khác rỗng nào của nhóm này. Chi phí khi giao nhiệm vụ cho một tập gồm $x$ người là $x^k$.

Hãy tính tổng chi phí trên tất cả các tập con khác rỗng có thể có, lấy phần dư cho ${10}^9+7$.

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên $N$ và $k$.

Dữ liệu ra

In ra một số nguyên duy nhất: tổng chi phí trên tất cả các tập con khác rỗng, lấy phần dư cho ${10}^9+7$.

Ràng buộc

• $1\le N\le {10}^9$
• $1\le k\le 5000$

Ví dụ