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

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