7. Obsadenie toboganov plavčíkmi

Za mestom vznikol nový aquapark. Hore na kopci sú štartovacie stanovištia a dole sú veľké bazény. Zo stanovíšť do bazénov vedú tobogany, na ktorých sa radostne šmýkajú deti. Občas, keď sa plavčík nepozerá, deti skúšajú všelijaké vylomeniny, spúšťajú sa dolu hlavou, po trojiciach, alebo brzdia, keď nemajú. Inokedy ani plavčík nepomôže, niektoré deti robia hlúposti len vtedy, keď ich plavčík vidí lebo je to vraj viac cool a väčšia pocta.

Samozrejme, keď deti skúšajú nezbedy, stávajú sa úrazy a to nerobí aquaparku dobrú povesť. Prevádzkovatelia aquaparku by radi vedeli, aká je celková bezpečnosť aquaparku počas jednej sezóny.

Na každé stanovisko a ku každému bazénu môžme aj nemusíme posadiť plavčíka. Rozloženie plavčíkov sa každú chvíľu mení, až sa postupne vystriedajú úplne všetky možnosti. Bezpečnosť jedného toboganu závisí len od toho, či na jeho hornom a dolnom konci sedí plavčík. Bezpečnosť aquaparku v konkrétnom okamihu je súčin bezpečností všetkých toboganov v tom okamihu.

Úloha

Máte zadaný bipartitný graf,¹ ktorý predstavuje náš aquapark. Hrany tohto grafu sú tobogany. Vrcholy tohto grafu sú bazény a štartovacie stanovištia a každý vrchol ofarbíme jednou z dvoch farieb – čiernou, ak vo vrchole sedí plavčík, a bielou, ak nesedí. Počet vrcholov označíme \(n\) a počet hrán \(m\).

Pre každú hranu \(e\) vedúcu medzi vrcholmi \(u_e\) a \(v_e\) poznáme 4 hodnoty \(b_{e00}\), \(b_{e01}\), \(b_{e10}\) a \(b_{e11}\), ktoré určujú, aká je bezpečnosť príslušnej hany podľa farieb jej koncových vrcholov.

• \(b_{e00}\) je bezpečnosť hrany \(e\), ak sú oba vrcholy \(u_e\), \(v_e\) biele.
• \(b_{e01}\) je bezpečnosť hrany \(e\), ak je vrchol \(u_e\) biely a \(v_e\) čierny.
• \(b_{e10}\) je bezpečnosť hrany \(e\), ak je vrchol \(u_e\) čierny a \(v_e\) biely.
• \(b_{e11}\) je bezpečnosť hrany \(e\), ak sú oba vrcholy \(u_e\), \(v_e\) čierne.

Všimnite si, že nehovoríme nič o tom, ktorý z vrcholov \(u\), \(v\) je začiatok toboganu a ktorý koniec.

Pozrime sa na všetkých \(2^n\) ofarbení grafu (pre všetky možnosti ako rozmiestniť plavčíkov) a pre každé ofarbenie vypočítajme súčin bezpečností všetkých \(m\) hrán. Keď tieto súčiny sčítame, dostaneme celkovú bezpečnosť aquaparku počas sezóny.

Vypočítajte túto celkovú bezpečnosť modulo \(10^9+7\).

Formát vstupu

Na prvom riadku vstupu sú čísla \(n\) a \(m\), (\(2\leq n\leq 40\), \(1\leq m\leq 100\)). Vrcholy očíslujeme postupne \(1\) až \(n\).

Nasleduje \(m\) riadkov a na každom je \(6\) čísel \(u_e\), \(v_e\), \(b_{e00}\),\(b_{e01}\),\(b_{e10}\),\(b_{e11}\) popisujúcich jednu hranu (\(1\leq u_e,v_e\leq n\), \(0\leq b_{eij}\leq 10^9\)).

Čiastočné body sa budú dať získať aj za riešenia, ktoré zvládajú len malé \(n,m\), prípadne malé hodnoty \(b\). Budú aj vstupy, v ktorých je celková bezpečnosť pomerne malá.

Formát výstupu

Vypíšte jedno celé číslo – celkovú bezpečnosť lunaparku počas sezóny modulo \(1\,000\,000\,007\).

Príklady

Input:

2 1
1 2 1 2 3 4

Output:

10

Input:

3 2
1 2 1 0 0 1
2 3 1 0 0 1

Output:

2