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\), separated by blanks.

Output

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

Limitations

\(1 \le A,B \le 5 \times 10^7\)

Samples

Sample #1

Input

2 3

Output

15

Hint

\(2^3 = 8\).
The natural divisors of \(8\) are: \({1,2,4,8}\). Their sum is \(15\).
\(15 \mod 9901 = 15\) (that should be output).

Simplified

求 \(A^B\) 的所有约数之和模 \(9901\)。

Source

算法竞赛进阶指南 POJ