题目描述
你算出了结果后,LCR 发现游戏匹配的随机对手「神犇」并没有走最优决策,于是她赢得了比赛并解密了数据。
现在 LCR 要将数据发送到 LOJ。然而近期网络环境不稳定,为了数据的安全传输,LCR 要在其中加入随机校验数列。
LCR 的随机数列 Xn 可以由四个参数 A,B,C,X0 描述:
Xn+1=((AXn+B)modC)+1 (n∈N)
传输完成后,要检测该数列的随机性以验证传输是否出现问题。于是 LCR 随机选取了序列中下标位于 [L1,R1] 的某个元素 Xi,以及下标位于 [L2,R2] 的某个元素 Xj,请你帮忙计算 ⌈XjXi+XiXj⌉ 的期望值。
为了避免精度误差,你只需要给出期望值乘以 (R1−L1+1)(R2−L2+1) 的值对 109+7 (一个质数)取模的值即可。
输入格式
共一行,包含八个正整数 A,B,C,X0,L1,R1,L2 和 R2,相邻两个数字之间恰好有一个空格。
输出格式
共一行,包含一个数字,表示答案。
样例 1
1 3 7 1 2 3 4 5
13
X=[1,5,2,6,3,7,⋯]
3 5 10 1 2 3 1 2
12
X=[1,9,3,5,⋯]
数据范围与提示
对于所有数据,1≤A,B,C,X0≤106,1≤L1≤R1≤1018,1≤L2≤R2≤1018。
Subtask # |
分值 |
A,B,C,X0 的限制 |
R1,R2 的限制 |
1 |
10 |
A,B,C,X0≤106 |
R1,R2≤103 |
2 |
20 |
A,B,C,X0≤105 |
R1,R2≤105 |
3 |
30 |
R1,R2≤1018 |
4 |
40 |
A,B,C,X0≤106 |