Велике відродження (срібло)

Через тривалу посуху пасовища фермера Джона залишилися без трави. Однак з наближенням сезону дощів настав час "обробляти рослинність". У сараї фермера Джона є два відра, в кожному з яких знаходяться насіння різної трави. Він хоче посадити траву на кожному зі своїх $n$ пасовищ. Кожне пасовище має бути засіяне рівно одним видом трави.

Фермер Джон, який займається молочним тваринництвом, хоче бути впевненим у тому, що він задовольнить особливі дієтичні потреби своїх $m$ корів. У кожної з його $m$ корів є два улюблених пасовища. У деяких корів є дієтичне обмеження: вони повинні постійно їсти тільки один вид трави — тому фермер Джон хоче, щоб на двох улюблених полях будь-якої такої корови був посаджений один і той же тип трави. У інших корів зовсім інші дієтичні обмеження, які вимагають від них їсти різні види трави. Щодо цих корів, фермер Джон, звісно ж, хоче, щоб на двох їхніх улюблених полях були різні типи трави.

Допоможіть фермеру Джону визначити кількість різних способів посадки трави на його $n$ пасовищах.

Вхідні дані

Перша рядок містить числа $n(2\le n\le 10^5)$ і $m(1\le m\le 10^5)$. Кожен з наступних $m$ рядків містить символ 'S' або 'D', за яким слідують два цілих числа в діапазоні $\mathrm{1...}n$, що описують пару пасовищ, які є улюбленими для однієї з корів фермера Джона. Символ 'S' означає, що корові на її двох улюблених пасовищах потрібна трава одного типу. Символ 'D' означає, що корові на пасовищах потрібні різні типи трави.

Вихідні дані

Виведіть кількість способів, якими фермер Джон може посадити траву на $n$ пасовищах. Запишіть відповідь у двійковому форматі.

Приклади