An application on Bertrand 's ballot theorem | PHP implementation of the approach ; Function to calculate factorial of a number mod 1000000007 ; Factorial of i = factorial of ( i - 1 ) * i ; ; Taking mod aint 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 ; Pre - compute factorials
< ? php $ mod = 1000000007 ; $ arr = array_fill ( 0 , 10001 , 0 ) ; function cal_factorial ( ) { global $ arr , $ mod ; $ arr [ 0 ] = 1 ; for ( $ i = 1 ; $ i <= 10000 ; $ i ++ ) { $ arr [ $ i ] = ( $ arr [ $ i - 1 ] * $ i ) % $ mod ; } } function mod_exponent ( $ num , $ p ) { global $ mod ; if ( $ p == 0 ) return 1 ; if ( ( $ p & 1 ) ) { return ( ( $ num % $ mod ) * ( mod_exponent ( ( $ num * $ num ) % $ mod , $ p / 2 ) ) % $ mod ) % $ mod ; } else if ( ! ( $ p & 1 ) ) return ( mod_exponent ( ( $ num * $ num ) % $ mod , $ p / 2 ) ) % $ mod ; } function getCount ( $ x , $ y ) { global $ arr , $ mod ; $ ans = $ arr [ $ x + $ y - 1 ] ; $ ans *= mod_exponent ( $ arr [ $ x ] , $ mod - 2 ) ; $ ans %= $ mod ; $ ans *= mod_exponent ( $ arr [ $ y ] , $ mod - 2 ) ; $ ans %= $ mod ; $ ans *= ( $ x - $ y ) ; $ ans %= $ mod ; return $ ans ; } cal_factorial ( ) ; $ x = 3 ; $ y = 1 ; print ( getCount ( $ x , $ y ) ) ; ? >