이분 그래프 색칠

Bobo는 $n$개의 정점을 가진 이분 그래프를 하나 받는다. 즉, 홀수 길이의 사이클이 없는 그래프이다.

각 정점을 검은색 또는 흰색으로 색칠한 뒤, 모든 간선의 값의 곱을 계산한다. 간선의 값은 양 끝 정점의 색에 따라 결정되므로, 하나의 간선에 대해 서로 다른 값이 $2 \times 2 = 4$가지 있을 수 있다.

이제 Bobo는 가능한 $2^n$가지 색칠 각각에 대해 그 곱을 모두 더한 값을 $(10^9+7)$로 나눈 나머지를 알고 싶어 한다.

첫째 줄에 정점의 수와 간선의 수를 나타내는 정수 $n, m$이 주어진다 ($2 \leq n \leq 40$, $1 \leq m \leq 100$).

정점은 편의상 $1, 2, \dots, n$으로 번호가 매겨진다.

다음 $m$개의 줄 각각에는 $6$개의 정수 $a_i, b_i, v_{i, 00}, v_{i, 01}, v_{i, 10}, v_{i, 11}$이 주어지며, 이는 정점 $a_i$와 $b_i$를 잇는 간선을 나타낸다 ($1 \leq a_i, b_i \leq n$, $0 \leq v_{i, 00}, v_{i, 01}, v_{i, 10}, v_{i, 11} \leq 10^9$).

• 정점 $a_i$와 $b_i$가 모두 흰색이면 $i$번째 간선의 값은 $v_{i, 00}$이다.
• 정점 $a_i$가 흰색이고 $b_i$가 검은색이면 값은 $v_{i, 01}$이다.
• 정점 $a_i$가 검은색이고 $b_i$가 흰색이면 값은 $v_{i, 10}$이다.
• 정점 $a_i$와 $b_i$가 모두 검은색이면 값은 $v_{i, 11}$이다.

합을 나타내는 정수 하나를 출력한다.