Tảo biển

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
admin
Dạng bài
Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

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

Test 1

Input 
3 2
Output 
15

Bình luận