P9777 [HUSTFC 2023] Fujisaki Hates Mathematics

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$.

A single line contains three integers $M\ (3\le M\le 998\,244\,353)$, $k\ (2\le k

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

Translated by ChatGPT 5