function to find moudulo inverse under 10 ^ 9 + 7
class gfg { public long MOD = 1000000007 ; public long modInv ( long x ) { long n = MOD - 2 ; long result = 1 ; while ( n > 0 ) { if ( ( n & 1 ) > 0 ) result = result * x % MOD ; x = x * x % MOD ; n = n / 2 ; } return result ; }