1 // File Name: temp.cpp  2 // Author: darkdream  3 // Created Time: 2014年09月17日 星期三 11时35分45秒  4   5 #include<vector>  6 #include<list>  7 #include<map>  8 #include<set>  9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 using namespace std; 26 LL n ,m;  27 LL ta,tb; 28 struct Matrix 29 { 30    LL  mat[2][2]; 31    void clear() 32    { 33       memset(mat,0,sizeof(mat)); 34    } 35    void output() 36    { 37      for(int i =0  ;i < n ;i ++) 38      { 39        for(int j = 0 ;j < n ;j ++) 40            printf("%I64d ",mat[i][j]); 41      printf("\n"); 42      } 43    } 44    void init() 45    { 46       clear(); 47       n = 2 ; 48       mat[0][0] = ta % m ;  49       mat[0][1] = 1; 50       mat[1][0] = tb % m ; 51       mat[1][1] = ta % m ; 52    } 53    Matrix operator *(const Matrix &b) const 54    { 55        Matrix ret; 56        ret.clear(); 57        for(int i = 0 ;i < n ;i ++) 58            for(int j = 0;j < n;j ++) 59            { 60                for(int k = 0 ;k < n ;k ++) 61                { 62                  ret.mat[i][j] =(ret.mat[i][j] + mat[i][k] * b.mat[k][j]) % m ; // 第I 行  第J  列         63                } 64            } 65        return ret; 66    } 67 }; 68 Matrix Pow( Matrix a ,LL t ) 69 { 70   Matrix ret; 71   ret.clear(); 72   for(int i = 0 ;i < n ;i ++) 73        ret.mat[i][i] = 1; 74   Matrix tmp = a;  75   while(t) 76   { 77       if(t&1) ret = ret * tmp; 78       tmp = tmp * tmp; 79       t >>=1; 80   } 81   return ret; 82 } 83 int main(){ 84     LL l ; 85     while(scanf("%I64d %I64d %I64d %I64d",&ta,&tb,&l,&m) != EOF) 86     { 87         Matrix  a; 88         a.init(); 89         if(l == 1) 90         { 91           printf("%I64d\n",(2* ta)%m); 92           continue; 93         } 94         a = Pow(a,l-1); 95         //a.output(); 96         LL ans = (((a.mat[1][0]  + (a.mat[1][1] * ta)%m)%m)*2)%m;  97         printf("%I64d\n",ans); 98     } 99     return 0;100 }