Vào một ngày đẹp trời khi đang học toán, p2o2HuaGiaBao là một cậu bé thông minh đã nghĩ ra một thuật toán có quy luật lạ lùng:
Ban đầu dãy \(A\) gồm không phần tử và có một con trỏ: |

• Bước \(1\): Ta thêm một số 0 vào sau con trỏ: 0|
• Bước \(2\): Ta di chuyển con trỏ một bước về phía trước (nếu đang ở cuối thì di chuyển về đầu): |0
• (Thực hiện như vậy đến khi đến hết vòng xoáy \(X\).

Định nghĩa: Một vòng xoáy là khi hay chỉ khi con trỏ | nằm ở vị trí đầu tiên.
Yêu cầu: Nhiệm vụ của bạn là tìm xem có bao nhiêu số 0 trong lần xoay thứ \(X\). Vì kết quả có thể rất lớn, nên bạn cần \(\text{mod}\) \(10^{9}+7\)

Input

• Gồm một dòng duy nhất là một số nguyên dương \(X\) \((1\le X\le 10^{18})\)

Output

• In ra một số duy nhất là số lượng số \(0\) trong lần xoay thứ \(X\).

Example

3

7