Function for finding inverse of a number iteratively Here we will find the inverse of 6 , since it appears as denominator in the formula of sum of squares from 1 to N
int inv ( int a ) { int o = 1 ; for ( int p = MOD - 2 ; p > 0 ; p >>= 1 ) { if ( ( p & 1 ) == 1 ) o = ( o * a ) % MOD ; a = ( a * a ) % MOD ; } return o ; }