Modular Fibonacci

#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)
{
    assert(p>=1);

    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 n,i,j,power_of_two;

    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;

    while(scanf("%lld%lld",&n,&power_of_two)==2)
    {
        if(n == 0 || n == 1)
        {
            printf("%d\n", n);
        }
        else
        {
            mod = pow(2,power_of_two);

            ans = power(n - 1);

            printf("%d\n", ans.v[0][0]);
        }
    }

    return 0;
}