Description

给定三个数$A$, $B$, $K$, 求 $A$的$B$次方除以$K$的余数 。

Format

Input

输入只有一行，为三个正整数$A(1 <= A <= 1018)$, $B(1 <= B <= 2×1018)$, $K(1 <= K <= 109)$。

Output

一个整数，$(A$ ^ $B)$ % $K$ 的值。

Samples

11 100 7

4