Trung Phan hôm nay bắt đầu buổi dạy lập trình vỡ lòng đầu tiên cho các em sinh viên khóa mới, K19. Bạn ấy dạy về công thức nghiệm để giải phương trình bậc hai có dạng ~x^2+ax+b=0.~ Tất nhiên, vì các test case ví dụ cho học viên mới làm quen thì cần phải rõ ràng, phải là số đẹp nên Trung muốn rằng hai nghiệm của phương trình thu được đều phải nguyên (không nhất thiết phân biệt). Cho biết rằng ~a,b~ là các số nguyên có giá trị tuyệt đối không vượt quá ~n~, bạn hãy giúp các học viên tính tổng tất cả các hệ số tự do (hệ số ~b~) của những phương trình bậc hai như thế nhé.

Input

Một dòng duy nhất là số nguyên dương ~n~ với ~1 \le n \le 10^{18}~.

Output

Đáp số của bài toán, chia lấy dư cho ~10^9+7.~

Các subtasks trong bài:

• Có 30% điểm ứng với ~n \le 10^4.~
• Có 40% điểm ứng với ~10^4 < n \le 5 \cdot 10^5.~
• Có 30% điểm ứng với ~5 \cdot 10^5 < n \le 10^{18}.~

Sample input 1:

1

Sample output 1:

1000000006

Sample input 2:

2

Sample output 2:

1000000004

Sample input 3:

90

Sample output 3:

105

Giải thích: trong VD1, ta thấy có các phương trình ~x^2-1=0~, ~x^2-x=0~, ~x^2+x=0~ là thỏa mãn, đáp số là ~-1+0+0=-1,~ (lấy modulo thì được ~10^9+6~) còn trong VD2, ta thấy ngoài các phương trình trên thì còn có ~x^2-2x=0~, ~x^2-2x+1=0~, ~x^2+2x+1=0~, ~x^2+2x=0~, ~x^2-x-2=0~, ~x^2+x-2=0~ với tổng hệ số tự do là ~-2~, kết hợp với tổng tính được ở trên là ~-1~ thì đáp số cần tìm là ~-3.~