玮哥的数学题
题号:NC220475
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

09级的玮哥是419的珍稀品种,因为他是数学专业的。虽说别人家的ACM都有很多数学专业的,但419总的来说数学专业的人比较稀少。
不过这两年我们有了一个更奇葩的专业。知道的小伙伴请把公屏打在弹幕上。
数学好才是真的好,玮哥也代表了419的巅峰,跟阿龙哥还有另外一位华少拿过区域赛的金奖。
玮哥对现在419的数学水平表示非常的关注,反手丢给你一个Fibonacci数列。

f(x) = 1  当 (x=1,2)
f(x) = f(x-1) + f(x-2)  当 (x>2)
对于给定的整数n 和 m,我们希望求出:
f(1) + f(2) + ... + f(n) 的值。但这个值可能非常大,所以我们把它对 f(m) 取模。
但这个数字依然很大,所以需要再对p 求模。




输入描述:

输入为一行用空格分开的整数n m p (0 < n, m, p < 10^18)

输出描述:

输出为1个整数,表示答案

示例1

输入

复制
2 3 5

输出

复制
0
示例2

输入

复制
15 11 29

输出

复制
25

备注:

玮哥的原题就是这样了。考虑到大家的实际水平,迅哥对数据规模做一个说明:
有8个测试点,m和n不超过100
有6个测试点:n和m不超过100
有5个测试点:m不超过90
有11个测试点:随意