#include <iostream>
#include <cassert>
#include <queue>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <ctime>
#include <map>
#include <set>
using namespace std;
// #define int long long
#define pii pair<int, int>
#define eb emplace_back
#define F first
#define S second
#define test(x) cout << "Test: " << x << '\n'
#define debug puts("qwq");
#define open(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define close fclose(stdin);fclose(stdout);
namespace FastIO {
template <typename T = int>
inline T read() {
T s = 0, w = 1;
char c = getchar();
while (!isdigit(c)) {
if (c == '-') w = -1;
c = getchar();
}
while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
return s * w;
}
template <typename T>
inline void read(T &s) {
s = 0;
int w = 1;
char c = getchar();
while (!isdigit(c)) {
if (c == '-') w = -1;
c = getchar();
}
while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
s = s * w;
}
template <typename T, typename... Arp> inline void read(T &x, Arp &...arp) {
read(x), read(arp...);
}
template <typename T>
inline void write(T x, char ch) {
if (x < 0) x = -x, putchar('-');
static char stk[25];
int top = 0;
do {
stk[top++] = x % 10 + '0', x /= 10;
} while (x);
while (top) putchar(stk[--top]);
putchar(ch);
return;
}
template <typename T>
inline void smax(T &x, T y) {
if (x < y) x = y;
}
template <typename T>
inline void smin(T &x, T y) {
if (x > y) x = y;
}
void quit() {
exit(0);
}
} using namespace FastIO;
const int N = 1e5 + 19, M = 20, mod = 1e9 + 7;
int lg[N], pw[M];
struct DSU {
int f[N];
void init(int n) { for (int i = 1; i <= n; ++i) f[i] = i; }
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
void merge(int x, int y) { f[find(x)] = find(y); }
} dsu[M];
signed main() {
pw[0] = 1;
for (int i = 2; i < N; ++i) lg[i] = lg[i >> 1] + 1;
for (int i = 1; i < M; ++i) pw[i] = pw[i-1] * 2;
int n, m; read(n, m);
for (int i = 0; i < M; ++i) dsu[i].init(n);
for (int i = 1; i <= m; ++i) {
int l1, r1, l2, r2; read(l1, r1, l2, r2);
int t = lg[r1 - l1 + 1];
dsu[t].merge(l1, l2);
dsu[t].merge(r1 - pw[t] + 1, r2 - pw[t] + 1);
}
for (int i = M - 1; i; --i) {
for (int j = 1; j <= n; ++j) if (dsu[i].find(j) != j) {
dsu[i-1].merge(j, dsu[i].find(j));
dsu[i-1].merge(j + pw[i-1], dsu[i].find(j) + pw[i-1]);
}
}
int cnt = 0;
for (int i = 1; i <= n; ++i) if (dsu[0].find(i) == i) cnt++;
int ans = 9;
for (int i = 1; i < cnt; ++i) ans = ans * 10 % mod;
write(ans, '\n');
return 0;
}
2 个赞
日。没开 long long。
3 个赞