Count of all possible ways to reach a target by a Knight | Python3 program to implement 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
Mod = int ( 1e9 + 7 ) NEW_LINE def power ( X , Y , Mod ) : NEW_LINE INDENT if Y == 0 : NEW_LINE INDENT return 1 NEW_LINE DEDENT p = power ( X , Y // 2 , Mod ) % Mod NEW_LINE p = ( p * p ) % Mod NEW_LINE if Y & 1 : NEW_LINE INDENT p = ( X * p ) % Mod NEW_LINE DEDENT return p NEW_LINE DEDENT def Inversefactorial ( N ) : NEW_LINE INDENT if N <= 0 : NEW_LINE INDENT return 1 NEW_LINE DEDENT fact = 1 NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT fact = ( fact * i ) % Mod NEW_LINE DEDENT return power ( fact , Mod - 2 , Mod ) NEW_LINE DEDENT def factorial ( N ) : NEW_LINE INDENT if N <= 0 : NEW_LINE INDENT return 1 NEW_LINE DEDENT fact = 1 NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT fact = ( fact * i ) % Mod NEW_LINE DEDENT return fact NEW_LINE DEDENT def nck ( N , K ) : NEW_LINE INDENT factN = factorial ( N ) NEW_LINE inv = Inversefactorial ( K ) NEW_LINE invFact = Inversefactorial ( N - K ) NEW_LINE return ( ( ( factN * inv ) % Mod ) * invFact ) % Mod NEW_LINE DEDENT def TotalWays ( N , M ) : NEW_LINE INDENT if ( N + M ) % 3 != 0 : NEW_LINE INDENT return 0 NEW_LINE DEDENT X = N - ( N + M ) // 3 NEW_LINE Y = M - ( N + M ) // 3 NEW_LINE if X < 0 or Y < 0 : NEW_LINE INDENT return 0 NEW_LINE DEDENT return nck ( X + Y , Y ) NEW_LINE DEDENT N , M = 3 , 3 NEW_LINE print ( TotalWays ( N , M ) ) NEW_LINE