题目描述

给定四个区间 $[a_1,a_2]$、$[b_1,b_2]$、$[c_1,c_2]$、$[d_1,d_2]$，请计算有多少个由正整数构成的四元组 $(a,b,c,d)$ 满足

$$a_1\leq a\leq a_2， ~b_1\leq b\leq b_2， ~c_1\leq c\leq c_2， ~d_1\leq d\leq d_2 $$

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

输入格式

第一行：两个正整数 $a_1$ 与 $a_2$； 第二行：两个正整数 $b_1$ 与 $b_2$； 第三行：两个正整数 $c_1$ 与 $c_2$； 第四行：两个正整数 $d_1$ 与 $d_2$。

输出格式

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

1 2
1 2
1 2
5 10

1

样例解释 1

仅有a=b=c=2且d=5时，四个数能够构成四边形的四条边长

1 2
1 2
1 2
1 2

16

样例解释 2

四个数任意取1或2都可以构成四边形

数据范围

• 对于 $30\%$ 的数据，$a_2,b_2,c_2,d_2\leq 100$；
• 对于 $50\%$ 的数据，$a_2,b_2,c_2,d_2\leq 1000$；
• 对于 $70\%$ 的数据，$a_2,b_2,c_2,d_2\leq 10000$；
• 对于 $100\%$ 的数据，$1\leq a_1\leq a_2\leq 10^5$，$1\leq b_1\leq b_2\leq 10^5$，$1\leq c_1\leq c_2\leq 10^5$，$1\leq d_1\leq d_2\leq 10^5$。