Fast matrix exponentiation with Modulo

fastmatexpo.cpp

//These are two functions which aid in raising a matrix data[][] to the power n using fast exponentiation techniques.
/*
Prerequisites:
// The matrix must be a 2x2 matrix.
1.  data[2][2]   ->The matrix which is required to be raised to nth power
2. result[2][2]  ->Initially make it equal to a 2x2 identity matrix.This matrix contains the required result.
3. n  -> The exponent
4. Also include -->    #define ll long long int
5.  Also include -->    #define mod_12 1000000007
<---  Note-All the above variables must be global   --->




*/


ll modulo_my(ll m, ll n) { return m >= 0 ? m % n : ( n - abs ( m%n ) ) % n; }

void multiply_mat(ll check)
{
	if(check==1)
	{
		ll aux[2][2];
		for(ll i=0; i<2; i++)
		{
			for(ll j=0; j<2; j++)
			{
				ll temp=0;
				for(ll k=0; k<2; k++)
				{
					temp += (modulo_my((modulo_my(result[i][k],mod_12) * modulo_my(data[k][j],mod_12)),mod_12));
				}
				aux[i][j]=(modulo_my(temp,mod_12));
			}
		}
		
		for(ll i=0; i<2; i++)
		{
			for(ll j=0; j<2; j++)
			{
				result[i][j] = aux[i][j];
			}
		}
	}
	else if(check==2)
	{
		ll aux[2][2];
		for(ll i=0; i<2; i++)
		{
			for(ll j=0; j<2; j++)
			{
				ll temp=0;
				for(ll k=0; k<2; k++)
				{
					temp += (modulo_my((modulo_my(data[i][k],mod_12) * modulo_my(data[k][j],mod_12)),mod_12));
				}
				aux[i][j]=(modulo_my(temp,mod_12));
			}
		}
		
		for(ll i=0; i<2; i++)
		{
			for(ll j=0; j<2; j++)
			{
				data[i][j] = aux[i][j];
			}
		}
	}
}
 








void fast_expo()
{
	while(n)
	{
		if(n&1)
		{
			multiply_mat(1);//result = result * data
		}
		multiply_mat(2);//data = data * data
		n >>=1;
	}
}