An application on Bertrand 's ballot theorem | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long NEW_LINE ll mod = 1000000007 ; ll arr [ 1000001 ] = { 0 } ; void cal_factorial ( ) { arr [ 0 ] = 1 ; for ( int i = 1 ; i <= 1000000 ; i ++ ) { arr [ i ] = ( arr [ i - 1 ] * i ) % mod ; } } ll mod_exponent ( ll num , ll p ) { 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 ; } ll getCount ( ll x , ll y ) { ll 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 ; } int main ( ) { cal_factorial ( ) ; ll x = 3 , y = 1 ; cout << getCount ( x , y ) ; return 0 ; }