Tảo biển sinh sản rất nhanh khi có môi trường thuận lợi với chúng và có những loài còn tiết ra môi trường những chất độc hại.

Một loại tảo nâu trong môi trường nước bị ô nhiễm nặ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 nước biển có bao nhiêu cá thể.

Input

• Gồm một dòng chứa 2 số nguyên \(n, k\) (\(1 \leq n \leq 1000, 1 \leq k \leq 10^5\)).

Output

• Ghi một số nguyên là số lượng cá thể tảo theo môđun \(10^9+7\).

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(N \leq 100, k \leq 10^3\)
• Subtask \(2\) (\(60\%\) số điểm): \(N \leq 1000, k \leq 10^5\)

Example

3 2 

15