链接：http://codeforces.com/problemset/problem/821/E

分析：由于有边界而且不同段边界还不同，直接算是不行的。。k是1e18，dp也不行。。用一个16维的向量表示某一列16个位置可能的种类数，到下一列的转移矩阵容易得到，而且在同一段里转移矩阵一样，直接用快速幂算出这一段结束的向量，然后继续推下一段结束的向量。注意特殊情况的处理。

1 #include
     
       2 #include
      
        3 using namespace std; 4 typedef long long ll; 5 const int maxn=105,p=1e9+7; 6 ll a[maxn],b[maxn],c[maxn]; 7 ll m[16][16],v[16]; 8 void initm(ll k){ 9     for(int i=0;i<16;i++)10         for(int j=0;j<16;j++)11             m[i][j]=0;12     m[0][0]=1;m[0][1]=1;13     for(int i=1;i
       
        0){17         m[k][k]=1;m[k][k-1]=1;18     }else{19         m[0][1]=0;20     }21 }22 void Copy(ll a[16][16],ll b[16][16]){23     for(int i=0;i<16;i++)24         for(int j=0;j<16;j++)25             a[i][j]=b[i][j];26 }27 void multiply(ll ma[16][16],ll mb[16][16],ll ans[16][16]){28     ll a[16][16],b[16][16];29     Copy(a,ma);Copy(b,mb);30     for(int i=0;i<16;i++){31         for(int j=0;j<16;j++){32             ans[i][j]=0;33             for(int k=0;k<16;k++)34                 ans[i][j]=(ans[i][j]+a[i][k]*b[k][j])%p;35         }36     }37 }38 void print(ll a[16][16]){39     for(int i=0;i<16;i++){40         for(int j=0;j<16;j++)41             cout<
        
         <<' ';42         cout<
         
          >n>>aim;80     for(int i=0;i
          
           >a[i]>>b[i]>>c[i];82 if(i==n-1)b[i]=aim;83 Update(b[i]-a[i],c[i]);84 }85 cout<
           
            <