An application on Bertrand 's ballot theorem | Python3 implementation of the approach ; Function to calculate factorial of a number mod 1000000007 ; Factorial of i = factorial of ( i - 1 ) * i ; Taking mod along with calculation . ; Function for modular exponentiation ; If p is odd ; If p is even ; Function to return the count of required permutations ; Calculating multiplicative modular inverse for x ! and multiplying with ans ; Calculating multiplicative modular inverse for y ! and multiplying with ans ; Driver Code ; Pre - compute factorials
mod = 1000000007 NEW_LINE arr = [ 0 ] * ( 1000001 ) NEW_LINE def cal_factorial ( ) : NEW_LINE INDENT arr [ 0 ] = 1 NEW_LINE for i in range ( 1 , 1000001 ) : NEW_LINE INDENT arr [ i ] = ( arr [ i - 1 ] * i ) % mod NEW_LINE DEDENT DEDENT def mod_exponent ( num , p ) : NEW_LINE INDENT if ( p == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( p & 1 ) : NEW_LINE INDENT return ( ( num % mod ) * ( mod_exponent ( ( num * num ) % mod , p // 2 ) ) % mod ) % mod NEW_LINE DEDENT elif ( not ( p & 1 ) ) : NEW_LINE INDENT return ( mod_exponent ( ( num * num ) % mod , p // 2 ) ) % mod NEW_LINE DEDENT DEDENT def getCount ( x , y ) : NEW_LINE INDENT ans = arr [ x + y - 1 ] NEW_LINE ans *= mod_exponent ( arr [ x ] , mod - 2 ) NEW_LINE ans %= mod NEW_LINE ans *= mod_exponent ( arr [ y ] , mod - 2 ) NEW_LINE ans %= mod NEW_LINE ans *= ( x - y ) NEW_LINE ans %= mod NEW_LINE return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT cal_factorial ( ) NEW_LINE x = 3 NEW_LINE y = 1 NEW_LINE print ( getCount ( x , y ) ) NEW_LINE DEDENT