当前没有测试数据。

5.斐波拉契

题目描述

令$x = \frac{1 + \sqrt{5}}{2}$，求$\lfloor x^{n} \rfloor \bmod m$。其中$\lfloor z \rfloor$表示对$z$下取整。

输入格式

一行两个整数$n$，$m$。

输出格式

一行一个整数表示答案。

数据范围与提示

对于$100\%$的数据，$1 \leq n \leq 10^{18}$，$1 \leq m \leq 998244353$。

样例

5 97

11