풀 심기

장기간의 가뭄으로 인해 도시의 $N$ 개의 정원은 풀이 모두 죽어있습니다. 그러나 장마철이 곧 시작하므로, '재배'의 시점이 다가왔습니다. 

도시 공원 관리자의 창고에는 두 가지 다른 종류의 잔디 씨앗이 각각 한 양동이씩 있습니다. 그는 $N$ 개의 정원 각각에 잔디를 심고자 하며, 각 정원에 심을 잔디의 종류는 정확히 하나를 선택하려고 합니다.

도시에서 관리자와 함께 $M$ 명의 정원을 관리해주는 주민들은 조금 특별한 조건에 따라 정원을 관리하도록 하고 싶습니다. 각 $M$명의 주민들은 각각 두 개의 좋아하는 정원을 가지고 있습니다. 일부 주민들은 그들이 일관되게 한 종류의 잔디만 관리해야 하는 제한이 있습니다. 따라서 관리자은 이러한 주민의 두 개의 좋아하는 목장에 같은 종류의 잔디가 심어지도록 하고 싶습니다.

 다른 주민들도 관리 제한이 있어, 그들에게는 다른 종류의 잔디를 관리할 것을 요구합니다. 이러한 주민들을 위해서는, 관리자은 당연히 그들의 두 개의 좋아하는 정원들이 다른 종류의 잔디를 포함하도록 하고 싶습니다.

관리자가 그의 $N$ 개의 정원에 잔디를 심는 방법이 얼마나 많은지 판단하는데 도움을 주세요.

입력의 첫 줄에는 $N$ ($2 \leq N \leq 10^5$) 과 $M$ ($1 \leq M \leq 10^5$) 이 포함됩니다. 다음 $M$ 줄 각각은 'S' 또는 'D' 중 하나인 문자와 모든 주민들이 좋아하는 두 개의 정원을 설명하는 $1 \ldots N$ 범위의 두 정수를 포함합니다. 

문자가 'S' 라면, 이 줄은 동일한 종류의 잔디를 심어야 하는 주민을 나타냅니다. 만약 문자가 'D' 라면, 이 줄은 다른 종류의 잔디를 관리하고 싶어하는 주민을 나타냅니다.

관리자가 그의 $N$ 개의 정원에 잔디를 심는 방법의 수를 출력하세요. 답을 이진법으로 작성해주세요.