An application on Bertrand 's ballot theorem | Java 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
class GFG { static long mod = 1000000007 ; static long [ ] arr = new long [ 1000001 ] ; static void cal_factorial ( ) { arr [ 0 ] = 1 ; for ( int i = 1 ; i <= 1000000 ; i ++ ) { arr [ i ] = ( ( arr [ i - 1 ] * i ) % mod ) ; } } static long mod_exponent ( long num , long p ) { if ( p == 0 ) return 1 ; if ( ( p & 1 ) != 0 ) { return ( ( num % mod ) * ( mod_exponent ( ( num * num ) % mod , p / 2 ) ) % mod ) % mod ; } else return ( mod_exponent ( ( num * num ) % mod , p / 2 ) ) % mod ; } static long getCount ( long x , long y ) { long ans = arr [ ( int ) x + ( int ) y - 1 ] ; ans *= mod_exponent ( arr [ ( int ) x ] , mod - 2 ) ; ans %= mod ; ans *= mod_exponent ( arr [ ( int ) y ] , mod - 2 ) ; ans %= mod ; ans *= ( x - y ) ; ans %= mod ; return ans ; } public static void main ( String [ ] args ) { cal_factorial ( ) ; long x = 3 , y = 1 ; System . out . println ( getCount ( x , y ) ) ; } }