Yet another Number Sequence

#include<bits/stdc++.h>

using namespace std;

struct matrix
{
    long long v[5][5];

    long long row,col;

} ans,mat;

long long mod;

matrix multiply(matrix a, matrix b)
{
    matrix r;

    for(int i=0; i<2; i++)
    {
        for(int j=0; j<2; j++)
        {
            long long sum = 0;

            r.v[i][j] = 0;

            for(int k=0; k<2; k++)
            {
                sum+=a.v[i][k]*b.v[k][j];

                sum%=mod;
            }

            r.v[i][j] = sum;
        }
    }

    return r;
}

matrix power(long long p)
{
    if(p==1)
    {
        return mat;
    }

    if(p%2==1)
    {
        return multiply(mat,power(p-1));
    }

    matrix ret = power(p/2);

    ret = multiply(ret,ret);

    return ret;
}

int main()
{
    long long tc,a,b,n,m,i,j;

    scanf("%lld",&tc);

    while(tc--)
    {
        scanf("%lld%lld%lld%lld",&a,&b,&n,&m);

        mat.row = mat.col = 2;

        for(i = 0; i < 2; ++i)
        {
            for(j = 0; j < 2; ++j)
            {
                mat.v[i][j] = 1;
            }
        }

        mat.v[1][1] = 0;

        mod = 1;

        for(i=0; i<m; i++)
        {
            mod*=10;
        }

        if(n<3)
        {
            if(n==0) printf("%lld\n",a);

            else if(n==1) printf("%lld\n",b);

            else if(n==2) printf("%lld\n",(a+b)%mod);
        }
        else
        {
            ans = power(n - 1);

            int res = b*ans.v[0][0] + a*ans.v[1][0];

            printf("%d\n",res%mod);
        }
    }

    return 0;
}