Returns modulo inverse of a with respect to m using extended Euclid Algorithm . Refer below post for details : https : www . geeksforgeeks . org / multiplicative - inverse - under - modulo - m /
int inv ( int a , int m ) { int m0 = m , t , q ; int x0 = 0 , x1 = 1 ; if ( m == 1 ) return 0 ;