题目描述

给定四个区间 [a1,a2]、[b1,b2]、[c1,c2]、[d1,d2]，请计算有多少个由正整数构成的四元组 (a,b,c,d) 满足a1≤a≤a2， b1≤b≤b2， c1≤c≤c2， d1≤d≤d2

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

输入格式

第一行：两个正整数 a1与 a2；
第二行：两个正整数 b1与 b2；
第三行：两个正整数 c1与 c2；
第四行：两个正整数 d1与 d2。

输出格式

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

数据范围

对于 30% 的数据，a2,b2,c2,d2≤100；

对于 50% 的数据，a2,b2,c2,d2≤1000；

对于 70% 的数据，a2,b2,c2,d2≤10000；

对于 100% 的数据，1≤a1≤a2≤10⁵，1≤b1≤b2≤10⁵，1≤c1≤c2≤10⁵，1≤d1≤d2≤10⁵。

样例数据

输入:

1 2

1 2

1 2

5 10

输出:

1

说明:

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

输入:

1 2

1 2

1 2

1 2

输出:

16

说明:

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