考虑如果只有$0$组边要怎么做。因为$N \leq 15$，考虑状压$DP$。设$f_i$表示当前的匹配情况为$i$时的概率($i$中$2^0$到$2^{N-1}$表示左半边的匹配情况，$2^N$到$2^{2N-1}$表示右半边的匹配情况)，转移就是随便取一条边将其起终边对应的位置去掉然后乘上$0.5$。
然而会发现这会重复转移，也就是说先选择$a$再选择$b$与先选择$b$再选择$a$在计算中被算作了两种情况，但实际上只能够算作一种。我们考虑固定$DP$的顺序。我们每一次选择$lowbit(i)$对应的点进行转移，这样转移就是左部分的点从小到大连边，转移也就不会重复了。
接着我们考虑$1$组边和$2$组边。首先我们考虑将这两组边中的两条边拆开考虑，这样会有：只选择第一条边参与贡献概率为$50\%$，只选择第二条边参与贡献概率为$50\%$，两条边同时参与贡献概率为$25\%$。发现只有两条边同时参与贡献时的概率是有问题的，所以我们考虑加上一条边。这一条边对应这一组的两条边，对于$1$组边给予其$25\%$的概率，对于$2$组边给予其$-25\%$的概率，这样概率就是对的了。这一条边要在较小的那一个左端点计算的时候进行计算。
上面那个不是很好理解，慢慢思考一下qwq
最后，$2^{30}$的数组是不可能开下的，考虑到有很多冗余状态，使用记忆化搜索就可以通过这道题了。
#include<bits/stdc++.h>
#define ld long double
//This code is written by Itst
using namespace std; inline int read(){
int a = ;
bool f = ;
char c = getchar();
while(c != EOF && !isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(c != EOF && isdigit(c)){
a = (a << ) + (a << ) + (c ^ '');
c = getchar();
}
return f ? -a : a;
} const int MAXN = * ;
const int MOD = 1e9 + ;
struct Edge{
int start , end , belStart , belEnd;
long long p;
}now[MAXN * ];
int range[] , num2[] , poww2[] , N , cnt , inv2 , inv4;
map < int , int > dp; inline void add(int x , int y , int belx , int bely , int p){
now[++cnt].start = x;
now[cnt].end = y;
now[cnt].belStart = belx;
now[cnt].belEnd = bely;
now[cnt].p = p;
} bool operator <(Edge a , Edge b){
return a.start < b.start;
} int dfs(int dir){
if(dp.count(dir))
return dp[dir];
if(!dir)
return ;
int t = num2[dir & -dir] , sum = ;
for(int i = range[t] ; i < range[t + ] ; ++i)
if(dir & poww2[now[i].end])
if(now[i].belStart == -)
sum = (sum + dfs(dir ^ poww2[t] ^ poww2[now[i].end]) * now[i].p) % MOD;
else
if((dir & poww2[now[i].belStart]) && (dir & poww2[now[i].belEnd]))
sum = (sum + dfs(dir ^ poww2[t] ^ poww2[now[i].end] ^ poww2[now[i].belStart] ^ poww2[now[i].belEnd]) * now[i].p) % MOD;
return dp[dir] = sum;
} inline int poww(long long a , int b){
int times = ;
while(b){
if(b & )
times = times * a % MOD;
a = a * a % MOD;
b >>= ;
}
return times;
} int main(){
#ifndef ONLINE_JUDGE
freopen("4547.in" , "r" , stdin);
//freopen("4547.out" , "w" , stdout);
#endif
N = read();
for(int i = ; i < N ; ++i)
num2[ << i] = i;
poww2[] = ;
for(int i = ; i < (N << ) ; ++i)
poww2[i] = poww2[i - ] << ;
inv2 = poww( , MOD - );
inv4 = poww( , MOD - );
for(int M = read() ; M ; --M){
int t = read() , x = read() - , y = read() + N - ;
add(x , y , - , - , inv2);
if(t){
int belx = read() - , bely = read() + N - ;
add(belx , bely , - , - , inv2);
if(belx < x){
swap(x , belx);
swap(y , bely);
}
if(belx != x && bely != y)
add(x , y , belx , bely , t == ? inv4 : MOD - inv4);
}
}
sort(now + , now + cnt + );
for(int i = ; i <= cnt ; ++i)
if(!range[now[i].start])
range[now[i].start] = i;
range[N] = cnt + ;
printf("%lld\n" , 1ll * dfs(( << (N << )) - ) * poww( , N) % MOD);
return ;
}