참/거짓 워크시트

Bob은 참/거짓 워크시트를 풀고 있다. 워크시트는 n개의 문제로 이루어져 있고, 각 문제의 답은 “참” 또는 “거짓”이다. 문제는 1번부터 n번까지 번호가 매겨져 있다. 문제가 Bob에게 너무 어려워서 조교 Alice가 Bob에게 m개의 힌트를 주었다. 각 힌트 i에 대해, Alice는 Bob에게 (양 끝을 포함하는) 문제 범위 [li, ri]를 주고, “그 범위의 모든 답이 같다”(즉, 전부 “참”이거나 전부 “거짓”) 또는 “그 범위의 답이 모두 같지는 않다”라고 알려준다. 주어진 힌트를 모두 만족하는 서로 다른 답 순서의 개수를 구하는 것을 Bob이 도와라. 답이 매우 클 수 있으므로 답을 109 + 7로 나눈 나머지를 출력한다.

입력의 첫 줄에는 두 개의 공백으로 구분된 정수 n과 m (1 ≤ n ≤ 5 000, 1 ≤ m ≤ 1 000 000)이 주어지며, 이는 각각 문제의 개수와 힌트의 개수이다. 다음 m개의 줄에는 각각 하나의 힌트가 인코딩되어 있으며, 두 개의 공백으로 구분된 정수 li와 ri (1 ≤ li ≤ ri ≤ n)와, 범위의 모든 답이 같으면 same, 범위의 답이 모두 같지 않으면(즉, 적어도 하나의 답이 “참”이고 적어도 다른 하나의 답이 “거짓”이면) different라는 단어가 주어진다.

주어진 힌트를 모두 만족하는 서로 다른 답 순서의 개수를 109 + 7로 나눈 나머지를 출력한다.

첫 번째 예제에서 힌트와 일치하는 네 가지 가능한 답 순서는 00000, 10000, 01111, 11111이며, 여기서 0은 “거짓” 답, 1은 “참” 답을 나타낸다. 두 번째 예제에서는 세 번째 힌트가 첫 번째와 두 번째 힌트와 충돌하므로, 모든 힌트를 만족하는 답 순서가 존재하지 않는다.