Flashback là loại virus máy tính sinh sản rất nhanh khi có môi trường thuận lợi và là một loại virus nguy hiểm, có tốc độ lây lan nhanh trong môi trường mạng.

Flashback lần đầu tiên được phát hiện vào năm 2011 bởi công ty diệt virus Intego dưới dạng một bản cài đặt Flash giả và chúng sinh sản theo quy luật sau:

• Ngày đầu tiên (ngày ~0~) có ~n~ cá thể ở mức ~1~.
• Ở mỗi ngày tiếp theo, mỗi cá thể mức ~i~ sinh ra ~i~ cá thể mức ~1~, các cá thể mới sinh sẽ sinh sôi, phát triển từ ngày hôm sau.
• Bản thân các cá thể mức ~i~ phát triển thành mức ~i + 1~ và chu kỳ phát triển trong ngày chấm dứt.

Yêu cầu

Hãy xác định sau ~k~ ngày trong môi trường mạng có bao nhiêu cá thể.

Input

Gồm một dòng chứa hai số nguyên ~n~ và ~k~.

• ~1 \le n \le 1000~
• ~1 \le k \le 10^5~

Output

Ghi một số nguyên là số lượng cá thể virus theo mô đun ~10^9 + 7~.

Subtasks

• 40% số điểm: ~n \le 100~, ~k \le 10^3~.
• 60% số điểm: ~n \le 1000~, ~k \le 10^5~.

Sample Input

5 3

Sample Output

65