题目描述

大家都知道 Fibonacci 数列吧，f1=1,f2=1,f3=2,f4=3,…,fn=fn−1+fn−2 。

现在问题很简单，输入 n 和 m ，求 fnmodm 。

输入格式

输入 n,m 。

输出格式

输出 fnmodm 。

样例

5 1000

5

提示

数据范围与提示：

对于 100% 的数据， 1≤n≤2×109,1≤m≤109+10 。