Source : 信息学奥赛一本通(提高篇)
Description
大家知道Fibonacci数列吧, f[1]=1, f[2]=1, f[3]=2, f[4]=3…, 也就是f[n]=f[n-1]+f[n-2],现在问题很简单,输入n和m,求第n项取模m。
Input
输入n, m
Output
输出第n项取模m
Sample Input
5 1000
Sample Output
5
Hint
【数据规模和约定】
1<=n<=2,000,000,000
1<=m<=1,000,000,010