Multiply two numbers recursively to solve this problem using some mod function.. below is the code segment. We will multiply two numbers eg. calculate half of multiplication and then add it twice and then for calculating halt of multiplication of two num, calculate 1/4 and then add 4 times and so on...
long long Multiply(long long a,long long b,long long mod)
{
long long x ,y ;
x=0;
y= a % mod;
while (b > 0)
{
if (b % 2 == 1)
{
x = (x + y) % mod;
}
y = (y * 2) % mod;
b /= 2;
}
return x % mod;
}