Masachika là một sinh kém năng động, có động lực với sở thích trở thành một otaku, thức khuya hầu hết các đêm. Chỗ ngồi của cậu nằm ở nửa cuối lớp cạnh cô bạn Alisa. Trái ngược với Masachika, Alisa là một học sinh ưu tú, người có điểm cao nhất trường và là thủ quỹ của Hội học sinh. Cô là một trong hai nàng công chúa xinh đẹp nhất trường và được mệnh danh là Công chúa cô độc. Đặc biệt, Masachika là người con trai duy nhất có thể gọi cô là Arya (tên thân mật ở Nga).
Một tuần trước Halloween Arya có ngỏ ý rủ Masachika đi hẹn hò vào dịp Halloween. Do Masachika vốn khá rảnh rỗi nên cậu không có lý do để từ chối buổi hẹn. Hôm đó, Yuki - em gái của Masachika đang mở một trò chơi khá thú vị. Cụ thể trò chơi có ~n~ gói kẹo, mỗi gói kẹo chứa khoảng ~1-3~ viên kẹo, và cũng có n chiếc bình có thể chứa tối đa ~m~ viên kẹo ở mỗi bình. Yuki muốn hai người tìm ra cách chia n gói kẹo vào các chiếc bình và mỗi bình sẽ chứa những gói kẹo liên tiếp nhau. Ví dụ: có ~5~ gói kẹo ~[1, 2, 3, 4, 5]~ có thể chia vào ~4~ bình với sức chứa là ~5~: ~[1, 2]~, ~[3]~, ~[4]~, ~[5]~
Yuki thách hai người có thể đếm số cách chia thoả mãn ở ~k~ bình (~k \le n~). Vì Masachika khá lười nên cậu định từ bỏ, nhưng cô bạn Arya là một người có tính hiếu thắng cao nên không dễ dàng như vậy. Arya chuyển sang chế độ trêu ghẹo bằng tiếng Nga: Разве ты не можешь это сделать? – [Cậu không làm được à ?], vì Masachika hiểu được tiếng Nga nên cậu không thể nào bỏ qua được. Các bạn hãy giúp cậu ấy giải bài toán trên để không bị cô bạn của mình khinh thường nhé! Hihi
Dữ liệu vào
- Dòng đầu chứa 2 số nguyên ~n~ và ~m~ (~n \le 10^3, 3 \le m \le 50~)
- Dòng thứ 2 chứa ~n~ số nguyên của mảng ~a~ (~a_i \le 3~)
Kết quả ra
In ra $n$ số tương ứng số cách chia vào $k$ bình thoả mãn (~1 \le k \le n)~. Vì kết quả có thể rất lớn nên bạn hãy in ra kết quả sau khi chia lấy dư cho ~10^{9} + 7~.
Ràng buộc:
- Subtask ~1~ (~30\%~): ~n = 10~
- Subtask ~2~ (~30\%~): ~n \le 100~
- Subtask ~3~ (~40\%~): không có ràng buộc gì thêm
Ví dụ
Dữ liệu
6 5
1 2 3 3 2 1
Kết quả
0 0 0 4 4 1
Giải thích
- Không có cách chia ~n~ gói kẹo vào ~1~, ~2~ hay ~3~ bình thoả mãn
- Có 4 cách chia ~n~ gói kẹo vào ~4~ bình:
- ~[1, 2], [3], [3, 2], [1]~
- ~[1, 2], [3], [3], [2, 1]~
- ~[1], [2, 3], [3, 2], [1]~
- ~[1], [2, 3], [3], [2, 1]~
- Có 4 cách chia ~n~ gói kẹo vào ~5~ bình:
- ~[1], [2], [3], [3, 2], [1]~
- ~[1], [2], [3], [3], [2, 1]~
- ~[1, 2], [3], [3], [2], [1]~
- ~[1], [2, 3], [3], [2], [1]~
- Có 1 cách chia ~n~ gói kẹo vào ~6~ bình:
- ~[1], [2], [3], [3], [2], [1]~
Bình luận