Antonija có \(N\) euro và phải dùng hết. Cô được giữ lại một số nguyên không âm \(k\) (\(0\le k\le N\)); số tiền \(N-k\) còn lại được chia đều cho hai con trai trong \(d\) ngày. Mỗi ngày, nếu một người nhận \(x\) euro thì người kia cũng nhận \(x\) euro, với \(x\) là số nguyên dương. Cô cũng có thể không chia tiền, tương ứng với \(k=N,d=0\). Hai cách chia khác nhau nếu khác \(k\), khác \(d\), hoặc dãy số tiền nhận mỗi ngày khác nhau. Hãy đếm số cách chia, lấy modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu chứa số nguyên \(N\) (\(1\le N\le10^{18}\)).

Dữ liệu ra

In số cách chia hợp lệ theo modulo \(10^9+7\).

Ràng buộc

Các giới hạn chính thức của dữ liệu được nêu đầy đủ trong phần Dữ liệu vào.

Phân nhóm

1. \(12\) điểm: \(N\le10\).
2. \(17\) điểm: \(N\le1000\).
3. \(36\) điểm: \(N\le10^6\).
4. \(5\) điểm: không có ràng buộc thêm.

Ví dụ

4

4

5

4

793

137435472

Nguồn

COCI 2025/2026 - Vòng 6, bài Džeparac.

Đề bài và dữ liệu kiểm thử được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.