Description

已知 Fibonacci 数列f1=1,f2=1,f3=2,f4=3,…,fn=fn−1+fn−2 。 现在问题是输入 n和 m，求 前n项的和取模 m。

Input Format

输入 n,m。

Output Format

输出前n项的和Sn mod m。

Sample

输入

5 000

输出

12

Hint

对于100%的数据，1<＝n<＝210^9,1<＝m<＝210^9+10。