| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 147 | 60 | 48 | 40.336% |
달구는 지난 2023년과 2024년에 열린 UDPC를 성공적으로 개최한 기념으로 윤이와 포닉스에게 보낼 자그마한 선물을 준비했다. 달구가 준비한 선물은 총 $N$개이고, 각 선물은 $1$번부터 $N$번까지의 번호가 붙어 있다.
달구는 준비한 모든 선물을 유니 또는 포닉스에게 보내려고 한다. 그러나 달구는 어떤 선물을 윤이에게 보낼지, 포닉스에게 보낼지를 아직 정하지 못했다. 달구는 $M$개의 조건을 세우고, 이 조건을 모두 만족하는 선에서 윤이와 포닉스에게 선물을 보내려고 한다. 달구가 세운 조건은 아래 세 가지 유형 중 하나이다.
U: $a$번 선물과 $b$번 선물은 모두 윤이에게 보내야 한다.D: $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을 출력한다.
6 3 1 4 U 2 5 D 3 6 P
2
9 6 1 7 D 6 7 D 1 6 P 3 7 U 2 4 D 5 8 P
4
3 4 1 2 P 1 3 P 1 2 P 2 3 P
1
7 7 1 2 D 2 3 D 3 4 U 4 5 D 5 6 D 6 7 D 1 7 P
0