Cho số nguyên dương N. Hãy cho biết có bao nhiêu dãy số nguyên dương có tổng các phần tử trong dãy bằng N.
Dữ liệu: Vào từ file văn bản COUNT.INP chứa duy nhất một số nguyên n <= 1018
Kết quả: Ghi ra file văn bản COUNT.OUT một số nguyên duy nhất là số dư của kết quả tìm được khi chia cho 123456789.
|
COUNT.INP |
COUNT.OUT |
|
3 |
4 |
Giải thích: Có 4 dãy số nguyên dương có tổng bằng 3 đó là:(1;1;1), (1;2), (2;1), (3).