Arrange the Schedule

Question

In Summer 2011, the ZJU-ICPC Team has a n-days training schedule. ZJU-ICPC Team has been divided into 4 Group: Akiba, BiliBili, CIA, Double(Group A, B, C, D). There is a group in charge of the training problems on each day. As the ICPC Team manager, you have to decide which team is in charge of the problems on each day. But there are something you should rememeber:

1. No team is able to provide problems on two adjacent days.
2. There are m days in the Summer 2011 that which group is in charge of the problems have been decided. (e.g. Akiba provides problems on day 1, BiliBili provides problems on day 6. And these can not be changed)

How many ways are there to arrange the schedule? Output the answer modulo 1000000007.

Input

There are multiple test cases(less than 50). Each case contains two integers n, m (1 ≤ n ≤ 10000000, 0 ≤ m ≤ 10), which indicate the number of days in Summer 2011 and the number of days that have been decided.
Following m lines. Each line contains one integer ai and one upper letter Ch ('A' ≤ Ch ≤ 'D'), indicate that on day ai (1 ≤ ai ≤ n), group Ch is in charge of the problems. We guarantee that all ai are distinct. There is a blank line after each input case.

Output

For each case, output a single line containing the answer, the number of the ways to arrange the schedule modulo 1000000007.

Sample Input

3 2
1 A
3 C

2 1
1 D

Sample Output

2
3

Answer 1

https://www.2cto.com/kf/201411/349919.html