Description

大家都知道 Fibonacci 数列吧，f1=1,f2=1,f3=2,f4=3,...,fn=f(n-1)+f(n-2)。

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

Input Format

输入n,m 。

Output Format

输出fn mod m。

Sample

输入

5 1000

输出

5

Hint

对于100%的数据， 1=<n<2*10^9,1=<m<10^9+10。