Böyük dirçəliş (gümüş)

Uzun müddət davam edən quraqlıq səbəbindən fermer Conun otlaqları otlarsız qaldı. Lakin yağış mövsümünün yaxınlaşması ilə "bitki örtüyünü becərmək" vaxtı gəldi. Fermer Conun anbarında iki vedrə var, hər birində müxtəlif ot toxumları var. O, otlarını $n$ otlağının hər birinə əkmək istəyir. Hər bir otlaqda yalnız bir növ ot əkilməlidir.

Südçülüklə məşğul olan fermer Con, $m$ inəyinin xüsusi qida tələblərini ödədiyinə əmin olmaq istəyir. Onun $m$ inəyinin hər birinin iki sevimli otlağı var. Bəzi inəklərin qida məhdudiyyəti var: onlar daim yalnız bir növ ot yeməlidirlər — buna görə də fermer Con istəyir ki, hər hansı belə inəyin iki sevimli sahəsində eyni növ ot əkilsin. Digər inəklərin isə tamamilə fərqli qida məhdudiyyətləri var, onlardan müxtəlif növ ot yeməyi tələb edir. Bu inəklərlə bağlı olaraq, fermer Con, əlbəttə ki, onların iki sevimli sahəsində fərqli növ otların olmasını istəyir.

Fermer Cona $n$ otlağında ot əkməyin müxtəlif yollarının sayını müəyyən etməyə kömək edin.

Giriş verilənləri

Birinci sətir $n(2\le n\le 10^5)$ və $m(1\le m\le 10^5)$ ədədlərini ehtiva edir. Növbəti $m$ sətirin hər biri, fermer Conun inəklərindən birinin sevimli otlaqları olan iki otlaq cütlüyünü təsvir edən 'S' və ya 'D' simvolunu və 1 ... n aralığında iki tam ədəd ehtiva edir. 'S' simvolu, inəyin sevimli otlaqlarında eyni növ otlara ehtiyacı olduğunu bildirir. 'D' simvolu isə inəyin otlaqlarda fərqli növ otlara ehtiyacı olduğunu bildirir.

Çıxış verilənləri

Fermer Conun $n$ otlağında ot əkmək üçün yolların sayını ikilik formatda yazın.

Nümunələr