MMOD29 - CALCULATE POW(2004,X) MOD 29

Consider a positive integer X, and let S be the sum of all positive integer divisors of 2004X. Your job is to determine S modulo 29 (the remainder of the division of S by 29).

Take X = 1 for an example. The positive integer divisors of 20041 are 1, 2, 3, 4, 6, 12, 167, 334, 501, 668, 1002 and 2004. Therefore S = 4704 and S modulo 29 is equal to 6.

Input

The input consists of several test cases. Each test case contains a line with the integer X (1 <= X <= 10000000). A test case of X = 0 indicates the end of input, and should not be processed.

Output

For each test case, in a separate line, please output the result of S modulo 29.

Sample

Input:
1
10000
0

Output:
6
10

Được gửi lên bởi:psetter
Ngày:2009-02-21
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Peiking 2004

hide comments
2018-11-07 09:28:08
ai làm được bài này bằng python hay C++ share em vào ạ! em cám ơn!
2017-11-05 16:06:29
nhật hào sạch
2017-09-04 10:28:12
kruskal + dijkstra heap + luong` + cap ghep + QHD trang thai + bignum = AC
2016-06-15 11:04:14 Lương Ðức Tuấn Ðạt
Tham khảo thuật toán và code tại: http://yeulaptrinh.pw/250/mmod29-spoj/
2015-11-26 10:28:29 xin đừng quên tôi
fermat nhỏ :v
2015-09-04 09:22:53
không cần dùng phi vẫn AC -_-
2014-04-17 13:56:29 zai zai
easy in python =))
2014-04-07 07:47:28 John and the cows


Last edit: 2014-04-26 17:19:44
2014-01-01 05:08:52 John and the cows
@Danh Nguyen
anh xem giùm a = 42874 b = 34 d = 12 sao dùng công thức này tính không dc ???
2013-12-31 11:44:32 John and the cows
@Lâm Nguyễn
nhỡ b và d cực lớn thì sao????
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.