根据题意，题目中所求的即为所有(n!)种完美匹配的各自的出现概率之和再乘上(2^n)的值。
发现(n)很小，考虑状压(DP)。设(f_{S,T})为左部图匹配情况为(S)，右部图匹配情况为(T)的期望，可以得到转移为：
[
f_{S,T}=sum_{x subseteqq S land y subseteqq T }f_{S oplus x,T oplus y} imes p_e
]
其中(x,y)为边(e)的在两个部图的两个端点，(p_e)为这条边的出现概率，转移的含义为加上(e)这条边后(x)和(y)实现了匹配。
发现直接这样转移会算重，所以要事先固定一种转移顺序，可以是每次在(S)中去除最高位来转移，也就是从低位向高位转移，这样就保证不会算重了。
然后考虑如何解决每条边的出现概率，第一组边不用特殊考虑，概率为(frac{1}{2})。考虑是否可以把第二组和第三组边也转化为第一种的形式。可以先将第二组和第三组边的两条边都以概率为(frac{1}{2})加入，对于第二组边，这时两条边同时出现的概率为(frac{1}{4})，不符合题目(frac{1}{2})的要求，因此再加入同时选这两条边的情况，概率为(frac{1}{4})，对于第三组边，再加入同时选这两条边的情况，概率为(-frac{1}{4})。根据期望的线性性，发现这样处理是正确的，并且恰好符合了题目的要求。
第二组和第三组边中，若两条边有交集，即两条边为一个点连向另外两个点，此时是不用加上同时选这两条边的情况的，因为题目所求为完美匹配，一个点匹配两个点的情况是不存在的。
处理完边后，记忆化搜索来实现状压(DP)即可。
(code:)
#include<bits/stdc++.h>
#define maxs 70010
#define p 1000000007
#define inv2 500000004
#define inv4 250000002
#define sta(x) (1<<(x-1))
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
int n,m,cnt;
map<int,ll> f[maxs];
struct node
{
ll s,t,v;
}e[maxs];
ll dp(int S,int T)
{
if(!S) return 1;
if(f[S].count(T)) return f[S][T];
for(int i=1;i<=cnt;++i)
{
ll s=e[i].s,t=e[i].t,v=e[i].v;
if((S|s)!=S||(T|t)!=T||S>=(s<<1)) continue;
f[S][T]=(f[S][T]+dp(S^s,T^t)*v%p)%p;
}
return f[S][T];
}
int main()
{
read(n),read(m);
for(int i=1;i<=m;++i)
{
int opt,x,y;
read(opt),read(x),read(y),e[++cnt]=(node){sta(x),sta(y),inv2};
if(opt)
{
read(x),read(y);
if(!((sta(x)&e[cnt].s)||(sta(y)&e[cnt].t)))
{
cnt++;
if(opt==1) e[cnt]=(node){sta(x)|e[cnt-1].s,sta(y)|e[cnt-1].t,inv4};
else e[cnt]=(node){sta(x)|e[cnt-1].s,sta(y)|e[cnt-1].t,p-inv4};
}
e[++cnt]=(node){sta(x),sta(y),inv2};
}
}
printf("%lld",dp((1<<n)-1,(1<<n)-1)*(1<<n)%p);
return 0;
}