Fibonacci第n项
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。
Format
Input
输入n, m
Output
输出第n项取模m
Sample 1
Input
5 1000
Output
5
Limitation
1s, 128MiB for each test case.
【数据规模和约定】
1<=n<=2,000,000,000
1<=m<=1,000,000,010