Description

On the weekend, little Keke takes part in a brain-power surfing challenge and finally reaches the last level, "Open Sesame." The electronic display on the door says: If you can correctly write on the door the sum of all positive integer divisors of $n^k$, and say "Open Sesame," the door will open freely.

For example: $n=2$, $k=3$, then $n^k=8$. Its positive divisors are $1, 2, 4, 8$. If Keke writes their sum $15$ on the door and then says "Open Sesame," the door will open automatically.

It is known that the values $n$ and $k$ on the door change from time to time. Please write a program to help Keke compute the answer within the allotted time, so as to win the final prize of the challenge.

Input Format

One line with two positive integers $n$ and $k$.

Output Format

One line with one integer representing the answer.

1 1

1

2 2

7

Hint

$1\le n \le 2^{16}$, $1\le k \lt 20$.

The answer has at most $100$ digits.

Translated by ChatGPT 5