Modular multiplication to avoid the overflow of multiplication Please see below for details https : www . geeksforgeeks . org / how - to - avoid - overflow - in - modular - multiplication /
long long int modMult ( long long int a , long long int b , long long int mod ) { long long int res = 0 ; a = a % mod ; while ( b > 0 ) { if ( b % 2 == 1 ) res = ( res + a ) % mod ; a = ( a * 2 ) % mod ; b /= 2 ; } return res % mod ; }