Description
一个长度为n的大数，用S1S2S3...Sn表示，其中Si表示数的第i位,S1是数的最高位，告诉你一些限制条件，每个条
件表示为四个数，l1，r1，l2，r2，即两个长度相同的区间，表示子串Sl1Sl1+1Sl1+2...Sr1与Sl2Sl2+1Sl2+2...S
r2完全相同。比如n=6时，某限制条件l1=1，r1=3，l2=4，r2=6，那么123123，351351均满足条件，但是12012，13
1141不满足条件，前者数的长度不为6，后者第二位与第五位不同。问满足以上所有条件的数有多少个。
Input
第一行两个数n和m，分别表示大数的长度，以及限制条件的个数。接下来m行，对于第i行,有4个数li1，ri1，li2
，ri2，分别表示该限制条件对应的两个区间。
1≤n≤10^5，1≤m≤10^5，1≤li1,ri1,li2,ri2≤n；并且保证ri1-li1=ri2-li2。
Output
一个数，表示满足所有条件且长度为n的大数的个数，答案可能很大，因此输出答案模10^9+7的结果即可。
Sample Input
4 2
1 2 3 4
3 3 3 3
1 2 3 4
3 3 3 3
Sample Output
90
HINT
Source
陈老师讲的一个题，思路还是很妙的。。。
考虑这个题最后要求的就是有多少种等价类，我们考虑用并查集来实现。。。
如果暴力做的话，给定[l1,r1],[l2,r2]，就把这两个区间中对应的位置用并查集并起来。。。
正解的话是ST表的鬼畜应用。。。每个ST[i][j]都代表一个点。。。。
对[l1,r1],[l2,r2],按ST表的那套理论，都拆为两个2^x的区间，然后把对应的区间的点用并查集并起来。。。
然后我们考虑把i从高层往低层下传额外关系，即从2^k -> 2^(k-1)，
因为ST[k][j] 可以拆为两个ST[k-1][...]。。。
如果在2^k层,ST[k][i]与ST[k][j]在同一集合，那么在2^(k-1),ST[k-1][i]和ST[k-1][j]在同一集合中，另外一个同理。。。
最后统计，2^0 层有多少个集合就行了。。。
// MADE BY QT666
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
const int N=200050;
const int Mod=1e9+7;
int pre[N],pre2[N],ST[20][N],n,m,tt,fa[N*20],tong[N],ans;
struct date{
int x,y;
}g[N*20],la[N*20];
void make_ST(){
pre[0]=1;for(int i=1;i<=18;i++) pre[i]=pre[i-1]<<1;
pre2[0]=-1;for(int i=1;i<=n;i++) pre2[i]=pre2[i>>1]+1;
for(int i=1;i<=n;i++) ST[0][i]=++tt;
for(int i=1;i<=18;i++)
for(int j=1;j<=n;j++){
if(j+pre[i]-1<=n){
ST[i][j]=++tt,g[tt].x=ST[i-1][j],g[tt].y=ST[i-1][j+pre[i-1]];
}
}
for(int i=1;i<=tt;i++) fa[i]=i;
}
int find(int x) {
if(x!=fa[x]) fa[x]=find(fa[x]);
return fa[x];
}
struct data{
int u,v;
};
data query(int l,int r){
int x=pre2[r-l+1];
int u=find(ST[x][l]),v=find(ST[x][r-pre[x]+1]);
return (data){u,v};
}
int main(){
scanf("%d%d",&n,&m);make_ST();
for(int i=1;i<=m;i++){
int l1,r1,l2,r2;scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
data x=query(l1,r1),y=query(l2,r2);
if(x.u!=y.u) fa[x.u]=y.u;
if(x.v!=y.v) fa[x.v]=y.v;
}
for(int i=18;i;i--){
for(int j=1;j<=n;j++){
int x=ST[i][j],y=find(x);
if(!la[y].x){
la[y].x=g[x].x,la[y].y=g[x].y;
}
else{
int u=find(la[y].x),v=find(g[x].x);
if(u!=v) fa[u]=v;
int u1=find(la[y].y),v1=find(g[x].y);
if(u1!=v1) fa[u1]=v1;
la[y].x=g[x].x,la[y].y=g[x].y;
}
}
}
ll ans=1;
for(int i=1;i<=n;i++){
if(!tong[find(ST[0][i])]){
tong[find(ST[0][i])]++;
if(i==1) (ans*=9)%=Mod;
else (ans*=10)%=Mod;
}
}
printf("%lld
",ans);
return 0;
}