Trong hội thi DH và ĐBBB 2017 có tổ chức cho các thí sinh trò chơi lắp ghép như sau: Cho K loại khối gỗ, mỗi khối gỗ không hạn chế số lượng và có chiều cao tương ứng là H1, H2, ..., Hk, dùng các khối gỗ này sếp chồng lên nhau để đạt đúng độ cao N. Mỗi thí sinh tham gia trò chơi là tìm số cách sắp xếp khác nhau từ các khối gỗ để đạt đúng độ cao N.
Yêu cầu: Cho N và chiều cao của mỗi loại khối gỗ, tìm số cách xếp từ các khối gỗ để đạt độ cao N.
Dữ liệu:
- Dòng 1: Ghi 2 số nguyên dương N và K.
- Dòng 2: Ghi K số H1, H2, ..., Hk, các số khác nhau từng đôi một
Kết quả:
Ghi ra một số nguyên là số cách xếp gỗ, vì số cách rất lớn nên lấy kết quả là phần dư của 109+7.
Input
3 2
1 2
Output
3
Ràng buộc:
- Có 30% số test ứng với 30% số điểm có K < N <= 10, 0 < Hi <= N
- Có 30% số test ứng với 30% số điểm có N<=104, K=3 và độ cao tương ứng là 1, 2 và 3, 0 < Hi <= N
- Có 40% số test ứng với 40% số điểm có N<=105, 3<K<=1000 và 0 < Hi <= N
Nguồn: DHBB 2017 (DNA)