19125번 - Bipartite Graph Coloring 다국어

문제

Bobo gets a bipartite graph with $n$ vertices (that is, a graph without odd cycles).

He colors each vertex into black or white, and then calculates the product of each edge's value. The value of an edge is determined by the colors of its two end points. Thus, there can be 2ドル \times 2 = 4$ different values associated to a given edge.

Now bobo would like to know the sum of products of all 2ドル^n$ possible coloring, modulo $(10^9+7)$.

입력

The first line contains 2ドル$ integers $n, m$ which denotes the number of vertices and edges (2ドル \leq n \leq 40,ドル 1ドル \leq m \leq 100$).

Vertices are numbered by 1,ドル 2, \dots, n$ for convenience.

Each of the following $m$ lines contains 6ドル$ integers $a_i, b_i, v_{i, 00}, v_{i, 01}, v_{i, 10}, v_{i, 11},ドル which denotes an edge between vertices $a_i$ and $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$).

• If vertices $a_i$ and $b_i$ are both white, the $i$-th edge's value is $v_{i, 00}$.
• If vertex $a_i$ is white and $b_i$ is black, the value is $v_{i, 01}$.
• If vertex $a_i$ is black and $b_i$ is white, the value is $v_{i, 10}$.
• If vertices $a_i$ and $b_i$ are both black, the value is $v_{i, 11}$.

출력

A single integer denotes the sum.

제한

힌트