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 \le N \le 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 \le a, c \le 10^4; 1 \le b \le 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 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 \le a, b, c \le 10^6~

Input:

2 1000000 10

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

Output:

6

Cho số nguyên dương ~N~. Hãy tính số dư của ~2^{3^N}~ khi chia cho 5.

Input

Số nguyên dương ~N~ ~(1 \le N \le 10^9)~

Output

In ra một số số nguyên duy nhất là kết quả của bài toán

Sample Input

2

Sample Output

2

Giải thích: ~3^2 = 9~, ~2^9 = 512~, 512 chia 5 dư 2.

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 được 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 vào: Dòng đầu tiên chứa một số nguyên dương N (~1 \le N \le 10^{14}~)

Dữ liệ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

Ouput 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 = 28. Kết quả là 28 - 8 = 20.