问题描述

给定整数 $N, M, P$。

求 $N$ 的 $P$ 次方除以 $M$ 的余数。

输入

输入数据从标准输入中按以下格式给出：

$N$ $M$ $P$

第一行为三个整数 $N, M, P (1≦N,M≦10^{9}, 1≦P≦10^{14})$，以空格分隔。

输出

输出 $N$ 的 $P$ 次方除以 $M$ 的余数。

解释

繰返し二乗法来自 AtCoder Inc.

示例输入 1

12 15 7

示例输出 1

3

$12$ 的 $7$ 次方是 $35831808$。它除以 $15$ 的余数是 $3$。

示例输入 2

123456789 234567894 6574837563712

示例输出 2

120678297

结果可能非常大。