Cổ phiếu
Đề bài
Mô tả
Gần đây, khi Crazy Dave đang học cách mua cổ phiếu, anh nhận được một tin nội bộ: cổ phiếu của công ty V sắp tăng vọt. Biết rằng giá cổ phiếu mỗi ngày là một số nguyên dương và, vì những lý do khách quan, giá cao nhất chỉ có thể là . Trong ngày tăng vọt, Dave quan sát được: giá cổ phiếu của mỗi ngày (trừ ngày đầu tiên) đều cao hơn ngày trước đó, và mức chênh lệch (tức là hiệu giữa giá của ngày hiện tại và giá của ngày trước đó) không vượt quá , với là một số nguyên dương. Các tham số này thỏa mãn .
Crazy Dave đã quên mất giá cụ thể của cổ phiếu trong ngày này, và giờ anh muốn biết có bao nhiêu cấu hình giá cổ phiếu trong ngày đó. Hai cấu hình được coi là khác nhau nếu có một ngày mà giá cổ phiếu theo hai cấu hình đó khác nhau.
Dữ liệu vào
Một dòng duy nhất chứa số nguyên dương (; ). không nhất thiết là số nguyên tố.
Dữ liệu ra
In ra một số nguyên là số cấu hình, lấy phần dư khi chia cho .
Ràng buộc
- .
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 7 3 2 1024 | 16 | Các cấu hình có thể là , , , , , , , , , , , , , , , . Có tổng cộng cấu hình. |
| 3001 400 6 9901 | 8669 | Số cấu hình rất lớn, chỉ in phần dư khi chia cho . |
Bình luận