小分分
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

给你n组线段,每组线段有 两个线段, 对于数轴上任意一点如果每组线段都能找到至少一个线段把这个点覆盖住,那么这个点我们称之为好点。当然有可能好点的覆盖方式不唯一,(比如可能有一组里面两个线段都能将其覆盖)现在让你求出所有好点的覆盖方式情况之和。由于答案可能过大,所以在模1e9+7下输出。
另外 对于一个线段左端点为l,右端点为r,对于任意一个点x,如果 l<=x<=r,那么我们认为x被这条线段覆盖
如果题面有点不理解可以去看样例解释

输入描述:

第一行一个整数n代表n组线段
接下来n行每行4个整数l1_i, r1_i,l2_i, r2_i分别代表每组的两个线段
1 \le n \le 5e5
1 \le l1_i \le r1_i \le 5e5
1 \le l2_i \le r2_i \le 5e5

输出描述:

一个整数代表答案
示例1

输入

复制
3
1 2 1 4
2 3 3 4
1 4 2 3

输出

复制
9

说明

对于1 第二组没有一个线段对其覆盖,所以1不是好点
对于2 第一组[1,2],[1,4]第二组[2,3]第三组[1,4],[2,3]都能将其覆盖,因此2是好点,并且它有4种覆盖方式
对于3 第一组[1,4]第二组[2,3],[3,4]第三组[1,4],[2,3]都能将其覆盖,因此3是好点,并且它有4种覆盖方式
对于4 第一组[1,4],第二组[3,4],第三组[1,4],都能将其覆盖,因此4是好点,并且它有1种覆盖方式
其他所有点都不是好点