Mid-Central USA Programming Contest 2019

Start

2019-11-02 17:30 UTC

Mid-Central USA Programming Contest 2019

End

2019-11-02 22:30 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -110 days 19:20:04

Time elapsed

5:00:00

Time remaining

0:00:00

Problem K
True/False Worksheet

/problems/truefalseworksheet/file/statement/en/img-0001.png
Photo by Pixabay

Bob is completing a true/false worksheet, consisting of a list of $n$ problems where each answer is either “true” or “false”. The problems are numbered from $1$ to $n$. They are too hard for Bob, so the TA, Alice, has given Bob $m$ hints. For each hint $i$, Alice gives Bob an (inclusive) range of questions $[l_ i, r_ i]$, and tells him either “all answers in the range are the same” (in other words, either all are “true”, or all are “false”); or “not all of the answers in the range are the same.” Help Bob count how many different answer sequences satisfy the given hints. Since this number may be huge, print the answer modulo $10^9+7$.

Input

The first line of the input contains two space-separated integers $n$ and $m$ $(1 \le n \le 5\, 000, 1 \le m \le 1\, 000\, 000)$, the number of problems and number of hints, respectively. The next $m$ lines each encode a hint, and contain two space-separated integers $l_ i$ and $r_ i$ $(1\leq l_ i \leq r_ i\leq n)$ followed by either the word same, if all answers in the range are the same, or different, if all answers in the range are not the same (i.e., at least one answer is “true” and at least one other answer is “false”).

Output

Print the number of different answer sequences satisfying all the hints, modulo $10^9+7$.

Sample Explanation

In the first sample, the four possible sequences consistent with the hints are 00000, 10000, 01111, and 11111 where 0 stands for a “false” answer and 1 stands for a “true” answer. In the second sample, the third hint conflicts with the first two hints, so no answer sequence exists consistent with all hints.

Sample Input 1 Sample Output 1
5 2
2 4 same
3 5 same
4
Sample Input 2 Sample Output 2
5 3
1 3 same
2 5 same
1 5 different
0