Find ways to arrange K green balls among N balls such that exactly i moves is needed to collect all K green balls | Python3 implementation of the approach ; To store the factorial and the factorial mod inverse of a number ; Function to find ( a ^ m1 ) % mod ; Function to find factorial of all the numbers ; Function to find the factorial mod inverse of all the numbers ; Function to return nCr ; Function to find ways to arrange K green balls among N balls such that we need exactly i moves to collect all K green balls ; Driver code ; Function call
N = 100005 NEW_LINE mod = ( int ) ( 1e9 + 7 ) NEW_LINE factorial = [ 0 ] * N ; NEW_LINE modinverse = [ 0 ] * N ; NEW_LINE def power ( a , m1 ) : NEW_LINE INDENT if ( m1 == 0 ) : NEW_LINE INDENT return 1 ; NEW_LINE DEDENT elif ( m1 == 1 ) : NEW_LINE INDENT return a ; NEW_LINE DEDENT elif ( m1 == 2 ) : NEW_LINE INDENT return ( a * a ) % mod ; NEW_LINE DEDENT elif ( m1 & 1 ) : NEW_LINE INDENT return ( a * power ( power ( a , m1 // 2 ) , 2 ) ) % mod ; NEW_LINE DEDENT else : NEW_LINE INDENT return power ( power ( a , m1 // 2 ) , 2 ) % mod ; NEW_LINE DEDENT DEDENT def factorialfun ( ) : NEW_LINE INDENT factorial [ 0 ] = 1 ; NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT factorial [ i ] = ( factorial [ i - 1 ] * i ) % mod ; NEW_LINE DEDENT DEDENT def modinversefun ( ) : NEW_LINE INDENT modinverse [ N - 1 ] = power ( factorial [ N - 1 ] , mod - 2 ) % mod ; NEW_LINE for i in range ( N - 2 , - 1 , - 1 ) : NEW_LINE INDENT modinverse [ i ] = ( modinverse [ i + 1 ] * ( i + 1 ) ) % mod ; NEW_LINE DEDENT DEDENT def binomial ( n , r ) : NEW_LINE INDENT if ( r > n ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT a = ( factorial [ n ] * modinverse [ n - r ] ) % mod ; NEW_LINE a = ( a * modinverse [ r ] ) % mod ; NEW_LINE return a ; NEW_LINE DEDENT def arrange_balls ( n , k ) : NEW_LINE INDENT factorialfun ( ) ; NEW_LINE modinversefun ( ) ; NEW_LINE for i in range ( 1 , k + 1 ) : NEW_LINE INDENT print ( ( binomial ( n - k + 1 , i ) * binomial ( k - 1 , i - 1 ) ) % mod , end = " ▁ " ) ; NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 5 ; k = 3 ; NEW_LINE arrange_balls ( n , k ) ; NEW_LINE DEDENT