题目背景

    业和渚在走廊里卿卿我我的走着

    渚:“没有空调好热啊!”

    业:“那你就别搂着我了。E班的特殊对待啊,唉,那个不是杀老师和小律吗?”

    渚:“我们去看看吧”

    杀老师:“小律,我的最高速度可是20马赫哦,计算速度一定比你快的『嘲讽脸』”

    律:“骑着摩的,挥着拳头要和我比一比,比就比谁怕谁,这不是业来了吗,业的数学这么好就让他来出道题吧!”

    业:“好啊,那么渚,你帮我想五个正整数,我来让他们算一个复杂的式子。”

   渚:“嗯嗯。”

         

题目描述

         定义正整数A:斐波那契数列模Amod的最小循环节

         定义正整数B:隔两个杀一个的约瑟夫环保证第alive号能够最后存活下来最少需要的总人数

         求式子\sum _{x=A}^{B}{((C-1)(C^x(\prod _{i = 1}^{m}(x+i) - \prod _{i = 0}^{m - 1}(x+i))+(\prod _{i = 1}^{m}(x+i))(C^x(C-1))+1)+\prod _{i = 1}^{m}(x+i) )}

    其中Cm是会直接告诉你的正整数

    结果很大,所以输出模MOD后的结果

    你的任务是给出正确答案来判断谁是正确的,由于杀老师和小律的计算速度飞快,所以你的答案也要计算的很快(正常机子约为0.2S/测试点,CH上为50ms/测试点)

输入格式

         输入共一行

         第一行有五个数分别是Amod,alive,C,mMOD

输出格式

         输出共一行

         第一行有一个数,即为答案模MOD后的结果

输入输出样例

 
输入样例1(stdin) 输出样例1(stdout)
1  2  3  4  1000000007
136086

 

输入样例2(stdin) 输出样例2(stdout)
451  792553  45  853  1000000007
942900926

数据范围

         会适当调整各个数的大小来保证答案不会超过long long并且尽量保证中间不会溢出,注意这里给出的是的A,B的数据范围而不是Amod,alive的范围

         10%的数据:1<=A<=B<=50

         60%的数据:1000000<=A<=B<=5000000

         20%的数据:1000000<=A<=B<=60000000

         10%的数据: 5000000000<=A<=B<=8000000000

PDF:pan.baidu.com/s/1i3w6b7B

本题出题人太弱所以报名人数太少,出题人已经弃疗了,有事烧纸就好