Count of all possible ways to reach a target by a Knight | C ++ Program to implement the above approach ; Function to return X ^ Y % Mod ; Base Case ; Function to return the inverse of factorial of N ; Base case ; Function to return factorial of n % Mod ; Base case ; Function to return the value of n ! / ( ( n - k ) ! * k ! ) ; Function to return the count of ways to reach ( n , m ) from ( 0 , 0 ) ; If ( N + M ) % 3 != 0 ; No possible way exists ; Calculate X and Y from the equations X + 2 Y = N and 2 X + Y == M ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int Mod = 1e9 + 7 ; int power ( int X , int Y , int Mod ) { if ( Y == 0 ) return 1 ; int p = power ( X , Y / 2 , Mod ) % Mod ; p = ( p * p ) % Mod ; if ( Y & 1 ) { p = ( X * p ) % Mod ; } return p ; } int Inversefactorial ( int N ) { if ( N <= 0 ) return 1 ; int fact = 1 ; for ( int i = 1 ; i <= N ; i ++ ) { fact = ( fact * i ) % Mod ; } return power ( fact , Mod - 2 , Mod ) ; } int factorial ( int N ) { if ( N <= 0 ) return 1 ; int fact = 1 ; for ( int i = 1 ; i <= N ; i ++ ) { fact = ( fact * i ) % Mod ; } return fact ; } int nck ( int N , int K ) { int factN = factorial ( N ) ; int inv = Inversefactorial ( K ) ; int invFact = Inversefactorial ( N - K ) ; return ( ( ( factN * inv ) % Mod ) * invFact ) % Mod ; } int TotalWaYs ( int N , int M ) { if ( ( N + M ) % 3 != 0 ) return 0 ; int X = N - ( N + M ) / 3 ; int Y = M - ( N + M ) / 3 ; if ( X < 0 Y < 0 ) return 0 ; return nck ( X + Y , Y ) ; } int main ( ) { int N = 3 , M = 3 ; cout << TotalWaYs ( N , M ) ; return 0 ; }