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ể.

Dữ liệu vào: Vào từ file văn bản SEAWEED.INP gồm:

• Một dòng chứa 2 số nguyên n và k (1 ≤ n ≤ 1000, 1 ≤ k ≤ 10⁵).

Dữ liệu ra: Đưa ra file văn bản SEAWEED.OUT  gồm:

• Một số nguyên – số lượng cá thể  tảo theo mô đun 10⁹+7.

Ví dụ:

Giới hạn:

- Có 40% số test ứng với 40% số điểm có N ≤ 100, k ≤ 10³

- Có 60% số test ứng với 60% số điểm có N ≤ 1000, k ≤ 10⁵