幂运算（Exponentiation）是一种数学运算，涉及将一个底数乘以自身若干次（指数次）以获得结果。在表达式 $a^n$ 中，$a$ 是底数，$n$ 是指数，它表示将 $a$ 乘以自身 $n$ 次。该运算的结果被称为 $a$ 的 $n$ 次幂。例如，$2^3 = 2 \times 2 \times 2 = 8$，$5^2 = 5 \times 5 = 25$。在这些例子中，第一个例子中 $2$ 是底数，$3$ 是指数；第二个例子中 $5$ 是底数，$2$ 是指数。幂运算是数学中的一项基本运算，常用于各种场景，如求解方程和密码学。

在许多密码学算法中，特别是基于数论的算法（如 RSA 和 Diffie-Hellman），模幂运算（modular exponentiation）是一项基本操作。模幂运算涉及将底数求指数幂后对模数取模。这种运算虽然计算量大，但即使对于非常大的数，也相对容易执行。

设 $x + \frac{1}{x} = \alpha$，其中 $\alpha$ 是一个正整数。请编写一个程序，在给定正整数 $\beta$ 和 $m$ 的情况下，计算 $x^\beta + \frac{1}{x^\beta} \bmod m$。

输入格式

输入只有一行，包含三个由空格分隔的正整数 $\alpha$、$\beta$ 和 $m$。

输出格式

输出 $x^\beta + \frac{1}{x^\beta} \bmod m$。如果存在多个解，你可以输出 $0$ 到 $m - 1$ 范围内的任意一个。

数据范围

$\alpha$、$\beta$ 和 $m$ 是小于 $2^{64}$ 的正整数。你可以假设 $x^\beta + \frac{1}{x^\beta}$ 是一个整数。

样例

输入样例 1

1 2 3

输出样例 1

2

输入样例 2

5 4 321

输出样例 2

206

输入样例 3

3 3 333

输出样例 3

18

输入样例 4

8 8 888

输出样例 4

626

说明

$x$ 可以是复数。例如，当 $\alpha = 1$ 时，$x$ 为 $\frac{1+\sqrt{3}i}{2}$ 或 $\frac{1-\sqrt{3}i}{2}$。然而，在本题中 $x^\beta + \frac{1}{x^\beta}$ 始终是一个整数。