Độ khó: Khá (3/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Hải là một chiến binh của một bộ lạc thời tiền sử. Nhiệm vụ của anh ta là đột nhập vào lãnh thổ của các bộ lạc khác và triệt hạ đi các thủ lĩnh bộ lạc này. Trong một lần hành động thành công, Hải đã cướp được ~N~ vũ khí. Theo thông tin của nhà tiên tri cùng bộ lạc, mỗi vũ khí có đánh một con số, vũ khí thứ ~i~ sẽ mang số ~a_i~. Được biết các vũ khí có mang số được tạo bởi từ các chữ số ~4~, ~7~ (ví dụ: ~4, 7, 44, 47, 74, 77, 444, 447, 474, 477, \ldots~) là các vũ khí đã bị nguyền rủa. Nhà tiên tri đã cho Hải biết rằng, một bộ vũ khí tốt là bộ vũ khí không chứa hai hay nhiều vũ khí bị nguyền rủa có cùng giá trị.

Trong số các vũ khí mà Hải mang về được, Hải không biết được rằng có bao nhiêu bộ vũ khí tốt có đúng ~K~ vũ khí.

Bạn được cho một dãy số ~a~ chứa các số tương ứng với các số trong bộ vũ khí của Hải lấy được. Nhiệm vụ của bạn là tính xem có bao nhiêu bộ vũ khí tốt có ~K~ vũ khí mà Hải lấy được theo lời khuyên của nhà tiên tri. Hai bộ trang bị khác nhau nếu có ít nhất 1 vũ khí mà bộ còn lại không có. Vì số bộ vũ khí có thể rất lớn nên hãy đưa ra kết quả với phép chia lấy dư cho ~1000000007~ ~(10^9 + 7)~.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N, K~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_i~, là dãy các số ~a~.

Kết quả

• Số bộ vũ khí tốt có ~K~ vũ khí (lấy dư cho ~10^9 + 7~).

Giới hạn

• ~1 \le K \le N \le 10^5~
• ~1 \le a_i \le 10^9~

Sample Input 1

3 2
10 10 10

Sample Output 1

3

Sample Input 2

4 2
4 4 7 7

Sample Output 2

4

Giải thích

Trường hợp đầu tiên: do không có vũ khí nào bị nguyền rủa nên ta có thể chọn bất cứ vũ khí nào vào bộ trang bị.

Trường hợp thứ hai: bộ 2 vũ khí phải gồm đúng một số ~4~ và một số ~7~: có ~2 \times 2 = 4~ bộ.