선물 보내기

달구는 지난 2023년과 2024년에 열린 UDPC를 성공적으로 개최한 기념으로 윤이와 포닉스에게 보낼 자그마한 선물을 준비했다. 달구가 준비한 선물은 총 $N$개이고, 각 선물은 $1$번부터 $N$번까지의 번호가 붙어 있다.

달구는 준비한 모든 선물을 유니 또는 포닉스에게 보내려고 한다. 그러나 달구는 어떤 선물을 윤이에게 보낼지, 포닉스에게 보낼지를 아직 정하지 못했다. 달구는 $M$개의 조건을 세우고, 이 조건을 모두 만족하는 선에서 윤이와 포닉스에게 선물을 보내려고 한다. 달구가 세운 조건은 아래 세 가지 유형 중 하나이다.

• $a$ $b$ U: $a$번 선물과 $b$번 선물은 모두 윤이에게 보내야 한다.
• $a$ $b$ D: $a$번 선물과 $b$번 선물은 윤이와 포닉스에게 각각 하나씩 보내야 한다.
• $a$ $b$ P: $a$번 선물과 $b$번 선물은 모두 포닉스에게 보내야 한다.

달구가 윤이와 포닉스에게 선물을 보낼 수 있는 서로 다른 방법의 수를 $10^9 + 7$로 나눈 나머지를 구해보자. 어떤 두 방법이 서로 다르다는 것은 두 방법에서 윤이 또는 포닉스가 받을 선물 번호의 집합이 서로 다름을 의미한다. 만약 모든 조건을 만족하도록 각 선물을 윤이 또는 포닉스에게 보낼 수 없는 경우에는 대신 0을 출력한다.

첫째 줄에 달구가 준비한 선물의 수 $N$과 선물을 보낼 때 고려해야 할 조건의 수 $M$이 공백으로 구분되어 주어진다. $(2 \le N \le 200\ 000; 1 \le M \le 200\ 000)$

다음 $M$개의 줄에는 두 선물의 번호 $a_i, b_i$와 U, D, P 중 하나의 문자가 공백으로 구분되어 주어진다. $(1 \le a_i < b_i \le N)$

입력에서 주어지는 모든 수는 정수이다.

달구가 윤이와 포닉스에게 선물을 보낼 수 있는 서로 다른 방법의 수를 $10^9 + 7$로 나눈 나머지를 출력한다. 만약 모든 조건을 만족하도록 각 선물을 윤이 또는 포닉스에게 보낼 수 없는 경우에는 대신 0을 출력한다.