#532. 「LibreOJ β Round #5」随机数列

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: tangjz

题目描述

你算出了结果后,LCR 发现游戏匹配的随机对手「神犇」并没有走最优决策,于是她赢得了比赛并解密了数据。

现在 LCR 要将数据发送到 LOJ。然而近期网络环境不稳定,为了数据的安全传输,LCR 要在其中加入随机校验数列。

LCR 的随机数列 Xn{X_n}Xn 可以由四个参数 A,B,C,X0A, B, C, X_0A,B,C,X0 描述:

Xn+1=((AXn+B)modC)+1 (nN)

传输完成后,要检测该数列的随机性以验证传输是否出现问题。于是 LCR 随机选取了序列中下标位于 [L1,R1][L_1, R_1][L1,R1] 的某个元素 XiX_iXi,以及下标位于 [L2,R2][L_2, R_2][L2,R2] 的某个元素 XjX_jXj,请你帮忙计算 ⌈XiXj+XjXi⌉\left\lceil \frac{X_i}{X_j} + \frac{X_j}{X_i} \right\rceilXjXi+XiXj 的期望值。

为了避免精度误差,你只需要给出期望值乘以 (R1−L1+1)(R2−L2+1)(R_1 - L_1 + 1)(R_2 - L_2 + 1)(R1L1+1)(R2L2+1) 的值对 109+710^9 + 7109+7 (一个质数)取模的值即可。

输入格式

共一行,包含八个正整数 A,B,C,X0,L1,R1,L2A, B, C, X_0, L_1, R_1, L_2A,B,C,X0,L1,R1,L2R2R_2R2,相邻两个数字之间恰好有一个空格。

输出格式

共一行,包含一个数字,表示答案。

样例

样例输入 1

1 3 7 1 2 3 4 5

样例输出 1

13

样例解释 1

X=[1,5,2,6,3,7,⋯]X = [1, 5, 2, 6, 3, 7, \cdots]X=[1,5,2,6,3,7,]

样例输入 2

3 5 10 1 2 3 1 2

样例输出 2

12

样例解释 2

X=[1,9,3,5,⋯]X = [1, 9, 3, 5, \cdots]X=[1,9,3,5,]

数据范围与提示

对于所有数据,1≤A,B,C,X0≤106,1≤L1≤R1≤1018,1≤L2≤R2≤10181 \leq A, B, C, X_0 \leq 10^6, 1 \leq L_1 \leq R_1 \leq 10^{18}, 1 \leq L_2 \leq R_2 \leq 10^{18}1A,B,C,X0106,1L1R11018,1L2R21018

Subtask # 分值 A,B,C,X0A,B,C,X_0A,B,C,X0 的限制 R1,R2R_1, R_2R1,R2 的限制
1 101010 A,B,C,X0≤106A, B, C, X_0 \leq 10^6A,B,C,X0106 R1,R2≤103R_1,R_2 \leq 10^3R1,R2103
2 202020 A,B,C,X0≤105A, B, C, X_0 \leq 10^5A,B,C,X0105 R1,R2≤105R_1,R_2 \leq 10^5R1,R2105
3 303030 A,B,C,X0≤105A, B, C, X_0 \leq 10^5A,B,C,X0105 R1,R2≤1018R_1,R_2 \leq 10^{18}R1,R21018
4 404040 A,B,C,X0≤106A, B, C, X_0 \leq 10^6A,B,C,X0106 R1,R2≤1018R_1,R_2 \leq 10^{18}R1,R21018