Талххүү маш хэцүү даалгавартай иржээ. Тэрээр түүнийгээ Алимхүүд ѳгч, гэтэл Алимхүү хэрхэн шийдэхийг мэдэхгүй байв. Түүнд туслах боломж байна уу?

$n × n$ шатрын хѳлѳг ѳгѳгдсѳн. Хѳлгийн нүд бүрт эсвэл 'x' үсэг, эсвэл 'o' үсэг, эсвэл хоосон байна. Нүд бүрийн хувьд хѳрш 'o' үсэгтэй нүдний тоо тэгш байхаар хоосон нүднүүдийг 'x' юмуу 'o' (тѳгсгѳлд нь нүд бүрт яг нэг үсэг байх ёстой) үсгээр дүүргэх боломжийн тоо хэд байх вэ? Боломжийн тоог $1000000007$ $(10^{9} + 7)$ тоонд хуваахад гарах үлдэгдлийг ол. Хѳрш нүд гэж ерѳнхий талтай нүднүүдийг хэлнэ.

Оролт

Эхний мѳрѳнд хѳлгийн хэмжээ, анх үсэгтэй байсан нүдний тоог илэрхийлэх $n$, $k$ ($1 ≤ n, k ≤ 10^{5}$) бүхэл тоо ѳгѳгднѳ.

Дараа нь $k$ мѳр байрлана. $i$-р мѳр хоёр тоо нэг үсэг агуулна: $a_{i}$, $b_{i}$, $c_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$; $c_{i}$ нь 'o' юмуу 'x'). Энэ нь $c_{i}$ үсэг $a_{i}$-р мѳр $b_{i}$-р баганын огтлол нүдэнд оршино гэсэн утгыг илтгэнэ. Ѳгсѳн нүднүүд ялгаатай.

Мѳрүүд дээрээс доош, баганууд зүүнээс баруун тийш $1$-ээс $n$ хүртэл дугаартай гэж үзнэ.

Гаралт

Бодлогын хариу болох ганц тоог хэвлэ.

Эхний жишээ тэстийн хувьд хоёр янзын боломжтой:

    xxo          xoo  
    xox          ooo  
    oxx          oox