대초원 복원 (실버)

긴 가뭄으로 Farmer John의 $N$개 목초지에는 풀이 하나도 남아 있지 않다. 곧 장마가 시작되니 이제 "복원"할 때가 되었다. Farmer John의 창고에는 서로 다른 종류의 풀 씨앗이 든 두 양동이가 있다. 그는 $N$개 목초지 각각에 정확히 한 종류의 풀을 심으려 한다.

낙농업자로서 Farmer John은 $M$마리 소의 다소 까다로운 식성 요구를 챙겨야 한다. $M$마리 소 각각에게는 가장 좋아하는 목초지가 두 개 있다. 일부 소는 한 종류의 풀만 계속 먹어야 한다는 식성 제한이 있어서, Farmer John은 그런 소가 좋아하는 두 목초지에 같은 종류의 풀을 심어야 한다. 다른 소들은 이와 달리 서로 다른 종류의 풀을 먹어야 한다. 이런 소에게는 당연히 좋아하는 두 목초지에 서로 다른 종류의 풀을 심어야 한다.

Farmer John이 $N$개 목초지에 풀을 심을 수 있는 서로 다른 방법의 수를 구해 주자.

첫째 줄에 $N$ ($2 \leq N \leq 10^5$)과 $M$ ($1 \leq M \leq 10^5$)이 주어진다. 그다음 $M$개 줄에는 각각 'S' 또는 'D'인 문자 하나와 $1 \ldots N$ 범위의 정수 두 개가 주어지는데, 이는 소 한 마리가 가장 좋아하는 두 목초지의 쌍을 나타낸다. 문자가 'S'이면 이 소는 두 목초지에 같은 종류의 풀을 심어야 하고, 'D'이면 서로 다른 종류의 풀을 심어야 한다.

Farmer John이 $N$개 목초지에 풀을 심을 수 있는 방법의 수를 이진수로 출력한다.