Count the number of ways to fill K boxes with N distinct items | Python3 program to calculate the above formula ; To store the factorials of all numbers ; Function to calculate factorial of all numbers ; Calculate x to the power y in O ( log n ) time ; Function to find inverse mod of a number x ; Calculate ( n C r ) ; Loop to compute the formula evaluated ; Add even power terms ; Subtract odd power terms ; Choose the k boxes which were used ; Driver code
mod = 1000000007 NEW_LINE factorial = [ 0 for i in range ( 100005 ) ] NEW_LINE def StoreFactorials ( n ) : NEW_LINE INDENT factorial [ 0 ] = 1 NEW_LINE for i in range ( 1 , n + 1 , 1 ) : NEW_LINE INDENT factorial [ i ] = ( i * factorial [ i - 1 ] ) % mod NEW_LINE DEDENT DEDENT def Power ( x , y ) : NEW_LINE INDENT ans = 1 NEW_LINE while ( y > 0 ) : NEW_LINE INDENT if ( y % 2 == 1 ) : NEW_LINE INDENT ans = ( ans * x ) % mod NEW_LINE DEDENT x = ( x * x ) % mod NEW_LINE y //= 2 NEW_LINE DEDENT return ans NEW_LINE DEDENT def invmod ( x ) : NEW_LINE INDENT return Power ( x , mod - 2 ) NEW_LINE DEDENT def nCr ( n , r ) : NEW_LINE INDENT return ( ( factorial [ n ] * invmod ( ( factorial [ r ] * factorial [ n - r ] ) % mod ) ) % mod ) NEW_LINE DEDENT def CountWays ( n , k ) : NEW_LINE INDENT StoreFactorials ( n ) NEW_LINE ans = 0 NEW_LINE i = k NEW_LINE while ( i >= 0 ) : NEW_LINE INDENT if ( i % 2 == k % 2 ) : NEW_LINE INDENT ans = ( ( ans + ( Power ( i , n ) * nCr ( k , i ) ) % mod ) % mod ) NEW_LINE DEDENT else : NEW_LINE INDENT ans = ( ( ans + mod - ( Power ( i , n ) * nCr ( k , i ) ) % mod ) % mod ) NEW_LINE DEDENT i -= 1 NEW_LINE DEDENT ans = ( ans * nCr ( n , k ) ) % mod NEW_LINE return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 5 NEW_LINE K = 5 NEW_LINE print ( CountWays ( N , K ) ) NEW_LINE DEDENT