Elektrik açarları

Fuadgilin evində $m$ lampa və $n$ elektrik açarı var. Elektrik açarları $1$-dən $n$-ə, lampalar isə $1$-dən $m$-ə nömrələnib. Hər bir elektrik açarı sıfır və ya daha çox lampaya bağlı ola bilər. Hər bir lampa isə iki elektrik açarına bağlıdır.

Elektrik açarı çevrildiyi zaman həmin elektrik açarına bağlı olan lampalar əgər yanılı vəziyyətdədirsə sönülü, sönülüdürsə yanılı vəziyyətə gəlir. Hazırda bəzi lampalar yanılı, bəziləri isə sönülüdür.

Fuad elektrik mühəndisi olmaq istədiyi üçün lampalarla oynamaq fikrinə düşüb. O, hər bir elektrik açarını ən çox bir dəfə çevirə bilər. Fuad bəzi elektrik açarlarını müəyyən ardıcıllıqla çevirərək elə etmək istəyir ki, bütün lampalar yanılı vəziyyətə gəlsin. Bunu etməyin mümkün olub-olmadığını müyyən edin. Əgər mümkündürsə, neçə fərqli üsulla etmək mümkün olduğunu tapın. Hər hansı iki üsul o halda fərqli sayılır ki, çevrilən elektrik açarları fərqli ardıcıllıq əmələ gətirsin.

Üsulların sayı böyük ola biləcəyindən onun $(10^9+7)$-yə qalığını tapın.

Giriş verilənləri

Birinci sətirdə boşluqla ayrılmış iki tam ədəd, $n(2\le n\le 500)$ və $m(1\le m\le n\cdot (n-1)/2)$, uyğun olaraq elektrik açarlarının və lampaların sayı verilir. Növbəti $m$ sətirdə lampalar təsvir edilir. $i$-ci lampa üç tam ədəd, $a_i,b_i(1\le a_i\ne b_i\le n,1\le i\le m)$ və $c_i(0\le c_i\le 1,1\le i\le m)$ ədədləri ilə verilir. Bu o deməkdir ki, $i$-ci lampa $a_i$ və $b_i(a_i\ne b_i)$ nömrəli elektrik açarlarına bağlıdır. $c_i$ isə onun başlanğıc vəziyyətini bildirir. $c_i=1$ olarsa lampa yanılı, $c_i=0$ olarsa sönülüdür.

İstənilən iki elektrik açarı üçün, onların hər ikisinə bağlı ən çox bir lampa olduğuna zəmanət verilir.

Çıxış verilənləri

Çıxışa birinci sətirdə əgər bütün lampaları yanılı vəziyyətə gətirmək mümkündürsə yay!, əks halda meh verin. Mümkün olduğu halda ikinci sətirdə üsulların sayını verin. Üsulların sayı böyük ola biləcəyindən onun $(10^9+7)$-yə qalığını çap edin.

Nümunələr

Birinci misalda bütün lampalar üç yoldan biri ilə yandırıla bilər:

• heç bir elektrik açarını çevirmədən;

• öncə $1$ sonra $2$ nömrəli elektrik açarını çevirməklə;

• öncə $2$ sonra $1$ nömrəli elektrik açarını çevirməklə;

Qiymətləndirmə

Bu məsələ aşağıdakı kimi $3$ alt tapşırıqdan ibarətdir. Alt tapşırıq üçün ballar yalnız bu alt tapşırığa aid bütün testlər uğurla keçdikdə verilir.

Bu məsələdə hər bir alt tapşırıq üçün, əgər həmin alt tapşırıqdakı bütün testlərdə sadəcə lampaları yanılı vəziyyətə gətirməyin mümkün olub-olmadığını düzgün müəyyən etsəniz, həmin alt tapşırığın balının $40$-ni əldə edəcəksiniz.

1. ($10$ bal): $h<9$;

2. ($20$ bal): $h<18$;

3. ($70$ bal): $Əlavəməhdudiyyətyoxdur$;