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

12

Limitation

1s, 128MiB for each test case.

1<=n<=2 000 000 000
1<=m<=1 000 000 010