Count different numbers possible using all the digits their frequency times | Python3 implementation of the above approach ; Initialize an array to store factorial values ; Function to calculate and store X ! values ; Iterative Function to calculate ( x ^ y ) % p in O ( log y ) ; x = x % p Update x if it is more than or equal to p ; If y is odd , multiply x with result ; y must be even now y = y >> 1 ; y = y / 2 ; Function that return modular inverse of x under modulo p ; Function that returns the count of different number possible by using all the digits its frequency times ; Preprocess factorial values ; Initialize the result and sum of aint the frequencies ; Calculate the sum of frequencies ; Putting res equal to x ! ; Multiplying res with modular inverse of X0 ! , X1 ! , . . , X9 ! ; Driver Code
MAXN = 100000 NEW_LINE MOD = 1000000007 NEW_LINE fact = [ 0 ] * MAXN ; NEW_LINE def factorial ( ) : NEW_LINE INDENT fact [ 0 ] = 1 NEW_LINE for i in range ( 1 , MAXN ) : NEW_LINE INDENT fact [ i ] = ( fact [ i - 1 ] * i ) % MOD NEW_LINE DEDENT DEDENT def power ( x , y , p ) : NEW_LINE INDENT while ( y > 0 ) : NEW_LINE INDENT if ( y & 1 ) : NEW_LINE INDENT res = ( res * x ) % p NEW_LINE DEDENT x = ( x * x ) % p NEW_LINE DEDENT return res NEW_LINE DEDENT def modInverse ( x , p ) : NEW_LINE INDENT return power ( x , p - 2 , p ) NEW_LINE DEDENT def countDifferentNumbers ( arr , P ) : NEW_LINE INDENT factorial ( ) ; NEW_LINE res = 0 ; X = 0 ; NEW_LINE for i in range ( 10 ) : NEW_LINE INDENT X += arr [ i ] NEW_LINE DEDENT res = fact [ X ] NEW_LINE for i in range ( 10 ) : NEW_LINE INDENT if ( arr [ i ] > 1 ) : NEW_LINE INDENT res = ( res * modInverse ( fact [ arr [ i ] ] , P ) ) % P ; NEW_LINE DEDENT DEDENT return res ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 0 , 2 , 0 , 0 , 7 , 4 , 0 , 0 , 3 ] NEW_LINE print ( countDifferentNumbers ( arr , MOD ) ) NEW_LINE DEDENT