众所周知772002很喜欢马尾，所以他决定画几幅马尾送给他的女朋友。
772002会画m种马尾，772002还有n张纸，n张纸分别编号1到n，每张纸上只能画一种马尾。
然而772002的女朋友只喜欢其中t种马尾。并且772002的女朋友只喜欢偶数（因为这象征着成对成双）。
772002想知道有多少种画法，使得n张纸画满并且自己女朋友喜欢的那t种马尾每种个数都恰好为偶数。
然而772002陪女朋友看电影去了，所以他把这个问题交给了你，你能解决吗？
Input
一行，三个整数m,n,t。
1-50组数据 m≤2，t≤m，n≤100
51-100组数据 m≤5，t≤m，n≤10000
101-300组数据 m≤10，t≤m，n≤1000000000
Output
一个整数,表示方案数，因为这个数比较大，所以输出对10007求余的结果。
Sample input and output
| Sample Input | Sample Output |
|---|---|
1 2 0 | 1 |
2 93 1 | 8605 |
Source
每周一题 div1
题解：
直接矩阵快速幂即可
#includeusing namespace std;const int mod = 10007;int m , n , t;struct mat{ int r , c , ele[12][12]; void init_dig(){ for(int i = 0 ; i < r ; ++ i) for(int j = 0 ; j < c ; ++ j) ele[i][j] = (i == j); } void init(){ memset( ele , 0 , sizeof( ele ) ); }};mat mul(const mat & a , const mat & b){ mat res ; res.r = a.r , res.c = b.c; for(int i = 0 ; i < a.r ; ++ i){ for(int j = 0 ; j < b.c ; ++ j){ int cnt = 0; for(int k = 0 ; k < a.c ; ++ k){ cnt += a.ele[i][k]*b.ele[k][j]; if( cnt >= mod ) cnt %= mod ; } res.ele[i][j] = cnt; } } return res;}mat pow( mat a , int b ){ mat res ; res.r = a.r , res.c = a.c; res.init_dig(); while( b ){ if( b & 1 ) res = mul( res , a ); b>>=1; a = mul( a , a ); } return res;}mat f;int main(int argc,char *argv[]){ scanf("%d%d%d",&m,&n,&t); f.r = t+1 , f.c = t+1; f.init(); for(int i = 0 ; i <= t ; ++ i){ f.ele[i][i] += ( m - t ); if(i > 0) f.ele[i][i-1] += i; if(i < t) f.ele[i][i+1] += (t-i); } mat ans ; ans.r = 1 , ans.c = t+1; ans.init(); ans.ele[0][t]=1; ans = mul( ans , pow( f , n ) ); printf("%d\n" ,ans.ele[0][t]); return 0;}