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