Problem Description

As is well known, Fujisaki scored very low in courses such as Calculus I (Part I), Calculus I (Part II), Linear Algebra, Discrete Mathematics I, and Probability Theory and Mathematical Statistics. This has led him to deeply resent advanced mathematics, so he has brought us a problem from elementary mathematics.

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

Input Format

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

Output Format

Output a single integer, which is the answer modulo \( M \).

Sample Input and Output

Sample Input #1

998244353 10 1

Sample Output #1

10

Sample Input #2

998244353 2 3

Sample Output #2

2

Sample Input #3

100 4 5

Sample Output #3

24

见题面 Input 部分

见题面 Output 部分