[HSG_DAN_24] Chiến binh

Xem dạng PDF
Gửi bài giải
Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, Python

Trong một vương quốc xa xưa, một vị tướng huyền thoại đang tập hợp một đội quân bất bại để chuẩn bị cho cuộc chiến vĩ đại. Đội quân này có một cơ chế huấn luyện đặc biệt, giúp binh lính nhanh chóng trưởng thành và chiêu mộ thêm chiến binh mới theo quy luật sau:

  • Ngày đầu tiên (ngày thứ ~0~), đội quân có ~n~ chiến binh ở cấp ~1~.
  • Ở mỗi ngày tiếp theo:
    • Mỗi chiến binh cấp ~i~ sẽ huấn luyện và chiêu mộ ~i~ tân binh (tất cả ở cấp ~1~). Những tân binh này sẽ bắt đầu huấn luyện và chiêu mộ lính mới từ ngày hôm sau.
    • Đồng thời, chiến binh cấp ~i~ sẽ trở nên mạnh mẽ hơn và thăng cấp lên cấp ~i + 1~.

Yêu cầu

Hãy xác định sau ~k~ ngày tổng số chiến binh có trong đội quân là bao nhiêu?

Dữ liệu đầu vào

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)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là kết quả bài toán chia lấy dư cho ~10^9 + 7~.

Ràng buộc dữ liệu

  • Có 40% số test với ~n \le 100;\ k \le 1000~.
  • Có 60% số test còn lại không giới hạn gì thêm.

Ví dụ

Ví dụ 1
INPUT
5 4
OUTPUT
170

Giải thích: Với ~5~ chiến binh ban đầu, sau ~4~ ngày tổng số chiến binh có trong quân đội là ~170~.

Bình luận

Hãy đọc nội quy trước khi bình luận.