Description

求A^B的所有约数（即因子）之和，并对其取模 9901再输出。（1<=A,B<=5×10^7）

Format

Input

输入两个自然数A，B。

Output

输出答案 mod 9901 。

Sample 1

Input

2 3

Output

15

【样例说明】
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).

Limitation

1s, 32MiB for each test case.

Source

poj1845