计算比赛の时间

题目背景

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

渚：“没有空调好热啊！”

业：“~~那你就别搂着我了。~~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) )}$

其中 $C$ 和 $m$ 是会直接告诉你的正整数

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

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

输入格式

输入共一行

第一行有五个数分别是 $Amod$ , $alive$ , $C$ , $m$ 和 $MOD$

输出格式

输出共一行

第一行有一个数，即为答案模 $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