CHIAKEO2 - Chia kẹo (bản trung)
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
0.05s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Ba anh em Hiếu, Kiệt và Hoàng đã đạt được thành tích cao trong học tập nên bố mẹ quyết định tặng cho cả ba anh em ~1~ túi kẹo, trong túi có ~N~ viên kẹo. Sau khi cả ba cùng thương lượng, vì Hiếu là anh cả, Kiệt là anh ba, Hoàng là em út nên Hiếu sẽ có số kẹo ít nhất và Hoàng sẽ có số kẹo nhiều nhất, không ai có cùng số kẹo và không ai không có viên kẹo nào. Dĩ nhiên tổng số kẹo của ba anh em gộp lại bằng ~N~.
Yêu cầu: Bạn hãy đếm số cách để chia kẹo sao cho thỏa mãn yêu cầu trên của ba anh em Hiếu, Kiệt, Hoàng nhé~!~
Input
- Số nguyên dương ~N (1 \le N \le 18\times 10^{18})~ là số viên kẹo trong túi kẹo.
Output
- In ra số cách chia theo yêu cầu của đề bài sau khi chia lấy dư cho ~10^9 + 7~.
Sample
Input #1
7
Output #1
1
Hint
Giải thích #1: Chỉ có ~1~ cách chia như sau:
- Hiếu ~1~ viên, Kiệt ~2~ viên, Hoàng ~4~ viên.
Bình luận
hello ae
Admin cho lên 2ms hoặc 5ms đi nộp gần trăm lần đúng nhiều nhất 55 case :)