Giải bài trực tuyến

English

Vietnamese

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mmod29

Xét số nguyên dương X và gọi S là tổng tất cả các ước dương của 2004^X .

Cần tính phần dư của S cho 29. Ví dụ, với X=1, các ước dương của 2004^1 là 1, 2, 3, 4, 6, 12, 167, 334, 501, 668, 1002 và 2004. Do đó S = 4704 và số dư của S chia cho 29 là 6.

Input

Gồm nhiều bộ test, mỗi bộ là một số nguyên X (1 <= X <= 10000000).

Bộ test với X = 0 để kết thúc chương trình và không cần xử lý.

Sample Input
1 
10000 
0

Output

Với mỗi bộ test, in ra một kết quả của số dư S chia cho 29 trên 1 dòng.

Sample Input
6 
10 

Note: làm quen với công thức tính tổng các ước số của 1 số - cách tính a^x mod p, cách tính (a^x-1)/(a-1) mod p