Start

2020-03-23 05:15 AKDT

Kattis Set 10

End

2020-03-30 01:30 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -249 days 13:21:37

Time elapsed

164:15:00

Time remaining

0:00:00

Problem J
Powers and Modulus

/problems/powers/file/statement/en/img-0001.jpg
Image by geralt

One day you and GTmac walk into a classroom and see a mysterious expression on the blackboard:

\[ (1^ b + 2^ b + \cdots + a^ b)~ \mathrm{mod}~ a \]

Upon seeing the expression GTmac shows an evil smile and challenges you: “Let me give you the values of $a$ and $b$ and let’s assume $b$ is an odd number. Want to bet who can evaluate this expression? The one who loses shall buy pizza for us tonight.”

Input

The input has two integers $a$ ($1 \leq a \leq 10^9$) and $b$ ($1\leq b\leq 99$, $b$ is odd) on a single line.

Output

Output the value of the expression with the given $a$ and $b$.

Sample Input 1 Sample Output 1
2 3
1
Sample Input 2 Sample Output 2
3 7
0
Sample Input 3 Sample Output 3
12345678 9
6172839