zoj 3538 Arrange the Schedule（矩陣快速冪）

zoj 3538 Arrange the Schedule（矩陣快速冪）

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 allai 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

Hint

Case 1:
2 ways: ABC, ADC.
Case 2:
3 ways: DA, DB, DC.

矩陣快速冪

剛開始想繁了，分段，每段算出一個值，最後相乘，結果寫出來wa掉了，檢查了半天也不知道哪裡寫跪了。

查了下題解，找了個好寫的思路。

當一天確定時，乘以矩陣b，

假設第i天確定是C

0 0 0 0

0 0 0 0

1 1 0 1

0 0 0 0

當一天不確定時，乘以矩陣a

0 1 1 1

1 0 1 1

1 1 0 1

1 1 1 0

ps：注意矩陣相乘的順序，在這裡坑了好久。

代碼：

#include 
#include 
#include 
#include 
using namespace std;
const int mod=1000000007;
struct matrix
{
    long long ma[5][5];
};
struct node
{
    int id;
    char s[5];
}op[20];
bool cmp(node a,node b)
{
    return a.id>1;
    }
    return ans;
}
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=0; i