📖 Bài giảng & lời giải: đây là Bài tập 3 trong bài giảng Chuyên đề nhập môn 10: Vét cạn thông minh trên blog Lập trình thuật toán – có lý thuyết, mô phỏng từng bước, gợi ý và code C++ / Python.

⚠️ 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 xem gợi ý và lờ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

Có $n$ con trâu và $n$ bó cỏ. Trâu đứng ăn 5 bó, trâu nằm ăn 3 bó, ba con trâu già ăn chung 1 bó. Hỏi có bao nhiêu cách chia số trâu thành ba loại (tổng số trâu đứng, trâu nằm, trâu già đúng bằng $n$) sao cho mỗi loại trâu có ít nhất một con và cả đàn ăn vừa hết đúng $n$ bó cỏ?

Dữ liệu vào

Một số nguyên $n$ ($1 \le n \le 10^6$).

Kết quả

• Dòng 1: số cách chia $c$.
• $c$ dòng tiếp theo, mỗi dòng gồm ba số nguyên là số trâu đứng, số trâu nằm, số trâu già của một cách chia, cách nhau một dấu cách. Các cách chia được in theo thứ tự số trâu đứng tăng dần.

Nếu không có cách nào, chỉ in một dòng chứa số 0.

Sample Input

100

Sample Output

3
4 18 78
8 11 81
12 4 84