Se consideră o matrice cu N linii şi N coloane (numerotate de la 1 la N). Fiecare element al matricei poate lua valoarea 0 sau 1. Se cunosc informaţii despre G submatrice ale matricii considerate. A i-a submatrice este definită de parametrii l1(i), c1(i), l2(i) şi c2(i) (1≤l1(i)≤l2(i)≤N ; 1≤c1(i)≤c2(i)≤N). Se ştie că xor-ul tuturor elementelor din submatricea i (elementele cuprinse între liniile l1(i) şi l2(i) inclusiv şi între coloanele c1(i) şi c2(i) inclusiv) este x(i) (evident, x(i) este 0 sau 1).
Fie NM numărul de matrice binare cu N linii şi N coloane pentru care toate informaţiile despre cele G submatrice sunt adevărate (există în total 2N∙N matrici binare cu N linii şi N coloane, dar informaţiile despre cele G submatrice nu sunt neapărat adevărate pentru toate aceste matrice).
Cerinţă
Determinaţi restul împărţirii lui NM la 34949.
Date de intrare
Prima linie a fişierului de intrare gxor.in conţine numerele întregi N şi G, separate printr-un spaţiu. A i-a dintre următoarele G linii (1<=i<=G) conţine cinci numere întregi, separate prin spaţii: l1(i) c1(i) l2(i) c2(i) x(i) (în această ordine).
Date de ieşire
În fişierul de ieşire gxor.out veţi afişa numărul de matrice posibile pentru care informaţiile despre toate cele G submatrici sunt corecte, modulo 34949.