UVa 10689 - Yet another Number Sequence

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%lld",&a)
#define sii(a,b) scanf("%lld %lld",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%lld\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100

ll n,m,a[MAX],b[MAX],MOD,c[2][2],z[2][2],ans[2][2];

void mul(ll a[2][2],ll b[2][2]){
    ll i,j,k;
    clr(c,0);
    f(i,0,2)
        f(j,0,2)
            f(k,0,2)
                c[i][j]=(c[i][j]+(a[i][k]*b[k][j])%MOD)%MOD;
}

void solve(ll n){
    ll i,j;
    ans[0][0]=1;ans[0][1]=0;ans[1][0]=0;ans[1][1]=1;
    while(n>0){
        if(n&1){
            mul(ans,z);
            f(i,0,2){
                f(j,0,2)
                    ans[i][j]=c[i][j];
            }
            n--;
        }
        else{
            mul(z,z);
            f(i,0,2){
                f(j,0,2)
                    z[i][j]=c[i][j];
            }
            n>>=1;
        }
    }
}

int main(){
    ll r,k,i,c=0,x=0,y=0,j,t,l,x1=0,y1=0;
    string p;

    si(t);
    while(t--){
        z[0][0]=1;z[0][1]=1;z[1][0]=1;z[1][1]=0;
        sii(x,y);
        sii(n,m);
        MOD=1;
        f(i,0,m){
            MOD*=10;
        }

        if(n>=2){
            solve(n-1);
            pi((ans[0][0]*y+ans[0][1]*x)%MOD);
        }
        else if(n==1)
            pi(y%MOD);
        else
            pi(x%MOD);
    }

    return 0;
}