MMOD29 - CALCULATE POW(2004,X) MOD 29

Giới hạn

• Thời gian: 0.833s
• Bộ nhớ: 1536MB
• Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

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

---

• Người up: vdmedragon
• Nguồn bài: Peiking 2004