I. Fujisaki 讨厌数学
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

众所周知，Fujisaki 在微积分（一）（上）、微积分（一）（下）、线性代数、离散数学（一）、概率论与数理统计这些课程中，只取得了非常低的分数，这导致他十分痛恨数学，因此他给大家带来了一道数学题。

已知 $$$x+x^{-1}=k$$$，其中 $$$k$$$ 是一个整数且 $$$k\ge 2$$$，Fujisaki 想让你帮他求出 $$$x^n+x^{-n}$$$ 的值。可以证明对于任意的整数 $$$n \ge 0$$$，这个值都是一个整数。由于结果可能会非常大，你只需要求出其对 $$$M$$$ 取模后的值。

Input

一行包含三个整数 $$$M\ (3\le M\le 998\,244\,353)$$$，$$$k\ (2\le k \lt M)$$$ 和 $$$n\ (0\le n\le 10^{18})$$$，其含义如题目所述。

Output

输出一个整数，表示答案对 $$$M$$$ 取模后的值。

Examples
Input
998244353 10 1
Output
10
Input
998244353 2 3
Output
2
Input
100 4 5
Output
24