Sunny đang học môn toán và hôm nay nhận được bài tập về cách tính tổng các ước số của một số nguyên dương. Nhiệm vụ là tìm tổng các số bé hơn hoặc bằng N và không phải là ước số của N.

Dữ liệu đầu vào: Dòng đầu tiên chứa một số nguyên dương N (1 ≤ N ≤ 10^14).

Dữ liệu đầu ra: In ra một số duy nhất, là kết quả của bài toán được chia lấy dư cho 10^9 + 7.

Input 01:

7

Output 01:

20

Giải thích: N=7: Các ước số của 7 là 1 và 7. Tổng các số từ 1 đến 7 là 1+2+3+4+5+6+7=28. Tổng các ước là 1+7=8. Kết quả là 28-8=20.

Input 01:

12

Output 02:

50

Giải thích: Với N=12: Các ước số của 12 là 1, 2, 3, 4, 6, 12. Tổng các số từ 1 đến 12 là 1+2+..+ 12=78. Tổng các ước là 1+2+3+4+6+12=28. Kết quả là 78-28=50.

Cho N số nguyên, bạn hãy tính tích các số này và chia dư cho 1086600067

Ràng buộc:

~1 \leq N \leq 10^5~

Các số là nguyên dương không quá ~10^6~

Input:

5
153 747 236 481 789

Output:

600664944

Tính a mũ b chia dư cho c với a, b, c là các số nguyên dương

Ràng buộc: ~1 \leq a, c \leq 10^4~; ~1 \leq b \leq 10^6~

Input 01:

2 1000000 10

Nhập như trên tức là 2 mũ 1000000 chia dư cho 10

Output 01:

6

Giải thích: 2 mũ 1000000 chia dư cho 10 kết quả sẽ bằng 6

Input 02:

5 999999 10

Output 02:

5

Cho a, b, c là các số nguyên dương, hãy tính a lũy thừa b chia dư cho c

Ràng buộc: ~1 \leq a, b, c \leq 10^6~

Input:

2 1000000 10

Tính 2 mũ 1000000 chia dư cho 10

Output:

6

Tìm K chữ số cuối cùng của N^M, kết quả có thế không đủ K chữ số. Ví dụ 9^5 = 59049 và K = 3 thì bạn chỉ cần in ra 49. Gợi ý : Tính N^M chia dư cho 10^K

Định dạng đầu vào: 3 số N, M, K

Ràng buộc:

~1 \leq N,M \leq 10^6~

~1 \leq K \leq 9~

In ra đáp án của bài toán

Input:

9 8 1

Output:

1

Cho N số nguyên, bạn hãy tính tổng các số này và chia dư tổng cho ~10^9 + 7 (1000000007)~

(Lưu ý: Mỗi số trong mảng được nhập ở một dòng)

Định dạng đầu vào:

• Dòng 1 là N: số lượng số nguyên

• Dòng 2 gồm N số nguyên cách nhau 1 khoảng trắng

Ràng buộc:

~1 \leq N \leq 10^5~

Các số là nguyên dương không quá 1~0^{16}~

Định dạng đầu ra: In ra đáp án của bài toán

Input:

5
534 7 669 826 610

Output:

2646

Bạn hãy tính N giai thừa và chia dư cho 10^9 + 7

Ràng buộc: ~1 \leq N \leq 10^6~

Input 01:

5

Output 01:

120

Input 02:

100

Output 02:

437918130

Cho 2 số N và M, hãy tìm ước chung lớn nhất của N và M. Chú ý ở đây N là một số nguyên lớn và M là một số nguyên 64 bit. Gợi ý: Dùng thuật toán Euclid và kỹ thuật chia dư với số nguyên lớn và số long long.

Ràng buộc: N có không quá 1000 chữ số; M là 1 số nguyên 64 bit.

Input 01:

30
4

Output:

2

Input:

12323213231234342341
34234343

Output:

1