2523. [HZOI 2016]定约servant

【题目背景】

    第五次圣杯之战，kito乱入，alice乱入(来自川原砾的Underworld)。

【题目描述】

     kito最终还是到达了重重障碍之后的房间。原来房间设了咒语，无法从里面打开，所以saber是被关在这里的。kito满心欢喜，打开房门，以为终于找到了saber，然而这个人虽然头发很像，但怎么看都不像是saber呢。kito看了一会，发现是alice。

    “请问，你是alice吗？”kito弱弱的询问靠墙坐着的金发少女。

    女孩抬起眼睑默默的看了kito一眼，忽然眼神一亮，瞬间蹦了起来，“啊！kirito!”

    “抱歉你认错人了，我是盗版kirito的kito。”kito回答。

“……”

    只听刷的一声，alice拔出佩剑指向kito的脖子，“你居然敢盗版我的kirito!”

    “什么你的kirito，明明是人家……”，kito说到这里立马闭嘴，改变话题，“话说好歹是我找到的你，不感谢我就算了，还拿剑指着我，我可告诉你，我！害！怕！了！”kito一如既往的认怂了呢。

    “唔，说的也是，”alice说，“你想让我怎么感谢你？”

    “跟我定契约吧。”kito刚说完，一股剑划破的凉气划过后颈，瞬间又怂了，“别别别！我错了我错了！”

    在瞪了kito半天之后，alice才默默的收回剑，“想让我当servant也可以，前提是你得能解开禁咒，毕竟我是乱入的，不是合法的servant。禁咒是这样的，是$fibonacci$数列的平方和。”

    “哦，这太简单了，套一个公式就好啦。”kito随口一回。

    “我还没有说完，$fibonacci$数列平方和只是指数而已，它的底数是：

                                     $\sum\limits_{i=1}^{m+1}\ [ gcd(i,m)==1 ] C(n,i-1)$ 。 ”

    “woc……”

    “考虑到你是个怂货，同时禁咒太长它本身也不好维护，你只需要将答案对p取模后的值告诉我就好。你若是能解开，我就答应做你的servant，你若是答不出来，我要替我的kirito打击盗版。”

原本kito已经认怂，一听alice的条件，瞬间来了精神，但是kito实在是太弱了，所以他只能拜托你，为了kito能有servant，希望你能把答案告诉他。

【输入格式】

   输入一共一行，有三个整数，分别为n,m,p。

【输出格式】

   共一行，为 $\sum\limits_{i=1}^{m+1}\ [ gcd(i,m)==1 ] C(n,i-1)$ 的($\sum\limits_{i=1}^{n} f[i]^2$)次方对p取模的值。f是$fibonacci$数列，前两项是1,1,$f[i]=f[i-1]+f[i-2]$。

【输入样例1】

   10 10 7

【输出样例1】

   1

【输入样例2】

10 10 9

【输出样例2】

 2

【数据范围】

数据100%保证p的质因子个数不会超过4个。

【来源】

   hzoi 2016