题目描述

幂运算是将底数提升至某个指数以得到结果的数学运算。在表达式 $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），模幂运算是基本操作。模幂运算涉及底数对指数进行幂运算后再对模数取模。该运算计算量较大，但即使对非常大的数字来说也相对容易实现。

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

输入格式

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

输出格式

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

1 2 3

2

5 4 321

206

3 3 333

18

8 8 888

626

提示

注意

$x$ 可以是复数。例如，若 $\alpha = 1$，则 $x$ 为 $\frac{1+\sqrt{3}i}{2}$ 或 $\frac{1-\sqrt{3}i}{2}$。但本题中 $x^\beta + \frac{1}{x^\beta}$ 始终是整数。

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

翻译由 DeepSeek V3.2 完成