1040 - 数论：矩阵快速幂：求斐波那契数列前n项和（大数据）

属如2个整数N,M，求斐波那契数列的前N项和，结果对M取模

Input

2个整数N ,N为 long long 类型，M为INT类型

Output

求前N项和，答案对M求模

Examples

Input

5 1000

Output

12
Time Limit 1 second
Memory Limit 128 MB
Discuss Stats
上一题 下一题