Description

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

现在问题很简单，输入n 和 m，求{fn} 的前n项和 sn mod m 。

Input Format

输入n,m 。

Output Format

输出前n项和 sn mod m 。

Sample

输入

5 1000

输出

12

Hint

对于全部数据，1=<n<2*10^9,1=<m<10^9+10。