构造矩阵 

0 1   *    a  =    b

1 1        b        a+b

然后高速幂

也能够依照题目所给的直接高速幂

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define N 30using namespace std;const int mod = 10000;struct matrix{    int a[2][2];}origin;int n=2,m;matrix multiply(matrix x,matrix y){    matrix temp;    memset(temp.a,0,sizeof(temp.a));    for(int i=0;i
          
           >=1; A=multiply(A,A); } return res;}void print(matrix x){ for(int i=0;i