题目描述

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

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

输入格式

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

输出格式

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

998244353 10 1

10

998244353 2 3

2

100 4 5

24