四边形(Quadrilateral)

题目描述

给定四个区间 [a₁,a₂]、[b₁,b₂]、[c₁,c₂]、[d₁,d₂]，请计算有多少个由正整数构成的四元组 (a,b,c,d) 满足

a₁ ≤ a ≤ a₂，b₁ ≤ b ≤ b₂，c₁ ≤ c ≤ c₂，d₁ ≤ d ≤ d₂

且 (a,b,c,d) 能够成为一个四边形的四条边长。

输入格式

第一行：两个正整数 a₁ 与 a₂； 第二行：两个正整数 b₁ 与 b₂； 第三行：两个正整数 c₁ 与 c₂； 第四行：两个正整数 d₁ 与 d₂。

输出格式

单个整数：表示有多少种 (a,b,c,d) 能够满足条件约束且能够构成四边形的四条边。由于答案可能很大，输出方案数模 10⁹+7 的余数。

数据范围

• 对于 30% 的数据，a₂,b₂,c₂,d₂ ≤ 100；
• 对于 50% 的数据，a₂,b₂,c₂,d₂ ≤ 1000；
• 对于 70% 的数据，a₂,b₂,c₂,d₂ ≤ 10000；
• 对于 100% 的数据，1 ≤ a₁ ≤ a₂ ≤ 10⁵，1 ≤ b₁ ≤ b₂ ≤ 10⁵，1 ≤ c₁ ≤ c₂ ≤ 10⁵，1 ≤ d₁ ≤ d₂ ≤ 10⁵。

样例输入 #1

1 2
1 2
1 2
5 10

样例输出 #1

1

样例1说明：仅有 a=b=c=2 且 d=5 时，四个数能够构成四边形的四条边长。

样例输入 #2

1 2
1 2
1 2
1 2

样例输出 #2

16

样例2说明：四个数任意取1或2都可以构成四边形。

知识点与难度

本题涉及的知识点从属于 GESP 8级，难度等级：⭐⭐⭐⭐。

测试点分布