Mẹ Antonija kiếm được ~n~ euro và phải tiêu hết số tiền đó càng sớm càng tốt. Bà có thể giữ lại cho mình một phần, nhưng phần còn lại phải được chia đều cho hai con trai trong một số ngày.

Trước hết, bà chọn một số nguyên không âm ~k~ với ~0 \le k \le n~ để giữ lại cho bản thân. Phần còn lại là ~n-k~ euro sẽ được chia cho hai con trong ~d~ ngày.

Mẹ Antonija cũng có thể không chia đồng nào cho hai con; đó là trường hợp ~n = k~ và ~d = 0~.

Nếu có chia tiền, thì ở mỗi ngày hai người con đều nhận cùng một số euro. Nếu một người con nhận ~x~ euro trong một ngày nào đó, thì người còn lại cũng nhận ~x~ euro trong ngày ấy, và ~x~ phải là một số nguyên dương. Tổng cộng hai người con cũng phải nhận bằng nhau.

Hai cách chia được xem là khác nhau nếu thỏa ít nhất một trong các điều kiện sau:

• số tiền giữ lại ~k~ khác nhau,
• số ngày ~d~ khác nhau,
• tồn tại ít nhất một ngày mà số tiền hai con nhận theo hai cách chia là khác nhau.

Hãy tính số cách khác nhau mà mẹ Antonija có thể chia tiền. Vì đáp án có thể rất lớn, hãy in kết quả theo modulo ~10^9 + 7~.

Input

Dòng đầu tiên chứa một số nguyên dương ~n~, là tổng số euro mẹ Antonija có.

Output

In ra một số nguyên duy nhất là số cách chia tiền hợp lệ.

Ràng buộc

• ~1 \le n \le 10^{18}~

Chấm điểm

• Subtask 1 (12 điểm): ~n \le 10~
• Subtask 2 (17 điểm): ~n \le 1000~
• Subtask 3 (36 điểm): ~n \le 10^6~
• Subtask 4 (5 điểm): Không có ràng buộc bổ sung.

Sample Input 1

4

Sample Output 1

4

Sample Input 2

5

Sample Output 2

4

Sample Input 3

793

Sample Output 3

137435472

Giải thích

• Ví dụ 1:
  • Nếu ~k = 4~, mẹ giữ toàn bộ tiền, nên chỉ có đúng ~1~ cách là không chia gì cho hai con.
  • Nếu ~k = 2~, còn lại ~2~ euro; cách duy nhất là ~d = 1~, mỗi người con nhận ~1~ euro.
  • Nếu ~k = 0~, còn lại ~4~ euro; có ~2~ cách hợp lệ: hoặc ~d = 1~ và mỗi người con nhận ~2~ euro, hoặc ~d = 2~ và mỗi ngày mỗi người con nhận ~1~ euro.
  • Nếu ~k = 1~ hoặc ~k = 3~, không có cách chia hợp lệ nào. Tổng cộng có ~1 + 1 + 2 = 4~ cách.