Problem B
Yet another Number Sequence
Input: standard input
Output: standard output
Time Limit: 3 seconds

Let's define another number sequence, given by the following function:

f(0) = a

f(1) = b

f(n) = f(n-1) + f(n-2), n > 1

When a = 0 and b = 1, this sequence gives the Fibonacci Sequence. Changing the values of a and b , you can get many different sequences. Given the values of a, b, you have to find the last m digits of f(n) .

Input

The first line gives the number of test cases, which is less than 10001. Each test case consists of a single line containing the integers a b n m. The values of a and b range in [0,100], value of n ranges in [0, 1000000000] and value of m ranges in [1, 4].

Output

For each test case, print the last m digits of f(n). However, you should NOT print any leading zero.

Sample Input Output for Sample Input

4

0 1 11 3

0 1 42 4

0 1 22 4

0 1 21 4

89

4296

7711

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          using namespace std; int a,b,n,m,mod; struct Mat{ int mat[2][2]; Mat(){ memset(mat,0,sizeof(mat)); } }; Mat operator *(Mat a,Mat b){ Mat c; for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) for(int m = 0; m < 2; m++){ c.mat[i][j] = (c.mat[i][j]+a.mat[i][m]*b.mat[m][j])%mod; } return c; } Mat pow_mod(Mat a,int n){ Mat res; for(int i = 0; i < 2; i++) res.mat[i][i] = 1; while(n){ if(n&1) res = res*a; n >>= 1; a = a*a; } return res; } int main(){ int ncase; cin >> ncase; while(ncase--){ cin >> a >> b >> n >> m; if(n==0){ cout<