Sumdiv

Time Limit: 1000 ms Memory Limit: 30000 KiB

Problem Description

Consider two natural numbers A and B. Let S be the sum of all natural divisors of A^B. Determine S modulo 9901 (the rest of the division of S by 9901).

Input

The only line contains the two natural numbers A and B, (0 <= A,B <= 50000000)separated by blanks.

Output

The only line of the output will contain S modulo 9901.

Sample Input

2 3

Sample Output

15

Hint

poj1845 有链接提示的题目请先去链接处提交程序,AC后提交到SDUTOJ中,以便查询存档。 2^3 = 8. The natural divisors of 8 are: 1,2,4,8. Their sum is 15. 15 modulo 9901 is 15 (that should be output).

Source

Romania OI 2002