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 <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
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<b.id;
}
matrix multi(matrix x,matrix y)
{
    matrix ans;
    memset(ans.ma,0,sizeof(ans.ma));
    for(int i=0; i<4; i++)
    {
        for(int j=0; j<4; j++)
        {
            if(x.ma[i][j])
            {
                for(int k=0; k<4; k++)
                {
                    ans.ma[i][k]=(ans.ma[i][k]+(x.ma[i][j]*y.ma[j][k])%mod)%mod;
                }
            }
        }
    }
    return ans;
}
matrix pow(matrix a,int m)
{
    matrix ans;
    for(int i=0; i<4; i++)
    {
        for(int j=0; j<4; j++)
        {
            if(i==j)
                ans.ma[i][j]=1;
            else
                ans.ma[i][j]=0;
        }
    }
    while(m)
    {
        if(m&1)
            ans=multi(a,ans);
        a=multi(a,a);
        m=m>>1;
    }
    return ans;
}
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=0; i<m; i++)
        {
            scanf("%d%s",&op[i].id,op[i].s);
        }
        sort(op,op+m,cmp);
        long long at[5];
        at[0]=at[1]=at[2]=at[3]=1;//初始矩阵
        int cur=1;
        matrix ans;
        for(int i=0;i<4;i++)
        {
            for(int j=0;j<4;j++)
            {
                if(i==j)
                ans.ma[i][j]=1;
                else
                ans.ma[i][j]=0;
            }
        }
        matrix a;
            for(int k=0;k<4;k++)
            {
                for(int j=0;j<4;j++)
                {
                    if(k==j)
                    a.ma[k][j]=0;
                    else
                    a.ma[k][j]=1;
                }
            }
        for(int i=0;i<m;i++)
        {
            int temp=op[i].id;
            if(temp==1)
            {
               // printf("jhfk\n");
                memset(at,0,sizeof(at));
                at[op[i].s[0]-'A']=1;
                continue;
            }
             matrix c;
            c=pow(a,temp-cur-1);
            ans=multi(c,ans);
            int ai=op[i].s[0]-'A';
            matrix b;
            memset(b.ma,0,sizeof(b.ma));
            for(int j=0;j<4;j++)
            {
                if(j!=ai)
                b.ma[ai][j]=1;
            }
            ans=multi(b,ans);
            cur=op[i].id;
        }
        if(cur<n)
        {
            matrix c;
            c=pow(a,n-cur);
            ans=multi(c,ans);
        }
        long long sum=0;
        for(int i=0;i<4;i++)
        {
            for(int j=0;j<4;j++)
            {
                sum=(sum+((long long)ans.ma[i][j]*at[j])%mod)%mod;
            }
        }
        printf("%lld\n",sum);
    }
    return 0;
}

zoj 3538 Arrange the Schedule（矩阵快速幂）