Problem Description

As everyone knows, Fujisaki got very low scores in courses such as Calculus (I) (Part 1), Calculus (I) (Part 2), Linear Algebra, Discrete Mathematics (I), and Probability Theory and Mathematical Statistics. This made him hate advanced mathematics very much, so he brings you an elementary math problem.

Given $x + x^{-1} = k$, where $k$ is an integer and $k \ge 2$, Fujisaki wants you to help him find the value of $x^n + x^{-n}$. It can be proven that for any integer $n \ge 0$, this value is an integer. Since the result may be very large, you only need to output it modulo $M$.

Input Format

A single line contains three integers $M\ (3\le M\le 998\,244\,353)$, $k\ (2\le k<M)$, and $n\ (0\le n\le 10^{18})$, with meanings as described in the statement.

Output Format

Output one integer, representing the answer modulo $M$.

998244353 10 1

10

998244353 2 3

2

100 4 5

24

Hint

Translated by ChatGPT 5