Number of ways to reach ( X , Y ) in a matrix starting from the origin | Java implementation of the approach ; To store the factorial and factorial mod inverse of the numbers ; Function to find ( a ^ m1 ) % mod ; Function to find the factorial of all the numbers ; Function to find the factorial modinverse of all the numbers ; Function to return nCr ; Function to return the number of ways to reach ( X , Y ) in a matrix with the given moves starting from the origin ; Driver code
import java . util . * ; class GFG { static long [ ] factorial = new long [ 1000005 ] ; static long [ ] modinverse = new long [ 1000005 ] ; static long mod = 1000000007 ; static int N = 1000005 ; static long power ( long a , long m1 ) { if ( m1 == 0 ) return 1 ; else if ( m1 == 1 ) return a ; else if ( m1 == 2 ) return ( a * a ) % mod ; else if ( ( m1 & 1 ) != 0 ) return ( a * power ( power ( a , m1 / 2 ) , 2 ) ) % mod ; else return power ( power ( a , m1 / 2 ) , 2 ) % mod ; } static void factorialfun ( ) { factorial [ 0 ] = 1 ; for ( int i = 1 ; i < N ; i ++ ) factorial [ i ] = ( factorial [ i - 1 ] * i ) % mod ; } static void modinversefun ( ) { modinverse [ N - 1 ] = power ( factorial [ N - 1 ] , mod - 2 ) % mod ; for ( int i = N - 2 ; i >= 0 ; i -- ) modinverse [ i ] = ( modinverse [ i + 1 ] * ( i + 1 ) ) % mod ; } static long binomial ( int n , int r ) { if ( r > n ) return 0 ; long a = ( factorial [ n ] * modinverse [ n - r ] ) % mod ; a = ( a * modinverse [ r ] ) % mod ; return a ; } static long ways ( long x , long y ) { factorialfun ( ) ; modinversefun ( ) ; if ( ( 2 * x - y ) % 3 == 0 && ( 2 * y - x ) % 3 == 0 ) { long m = ( 2 * x - y ) / 3 ; long n = ( 2 * y - x ) / 3 ; System . out . println ( n + m + " ▁ " + n ) ; return binomial ( ( int ) ( n + m ) , ( int ) n ) ; } return 0 ; } public static void main ( String [ ] args ) { long x = 3 , y = 3 ; System . out . println ( ways ( x , y ) ) ; } }