Count of distinct numbers formed by shuffling the digits of a large number N | Recursive function to return the value of ( x ^ n ) % m ; Base Case ; If N is even ; Else N is odd ; Function to find modular inverse of a number x under modulo m ; Using Fermat 's little theorem ; Function to count of numbers formed by shuffling the digits of a large number N ; Modulo value ; Array to store the factorials upto the maximum value of N ; Store factorial of i at index i ; To store count of occurrence of a digit ; Increment the count of digit occured ; Assign the factorial of length of input ; Multiplying result with the modulo multiplicative inverse of factorial of count of i ; Print the result ; Given number as string ; Function call
def modexp ( x , n , m ) : NEW_LINE INDENT if ( n == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT else : NEW_LINE INDENT if ( n % 2 == 0 ) : NEW_LINE INDENT return modexp ( ( x * x ) % m , n / 2 , m ) ; NEW_LINE DEDENT else : NEW_LINE INDENT return ( x * modexp ( ( x * x ) % m , ( n - 1 ) / 2 , m ) % m ) NEW_LINE DEDENT DEDENT DEDENT def modInverse ( x , m ) : NEW_LINE INDENT return modexp ( x , m - 2 , m ) NEW_LINE DEDENT def countNumbers ( N ) : NEW_LINE INDENT m = 1000000007 NEW_LINE factorial = [ 0 for x in range ( 100001 ) ] NEW_LINE factorial [ 0 ] = 1 ; NEW_LINE for i in range ( 1 , 100001 ) : NEW_LINE INDENT factorial [ i ] = ( factorial [ i - 1 ] * i ) % m NEW_LINE DEDENT count = [ 0 for x in range ( 10 ) ] NEW_LINE for i in range ( 0 , 10 ) : NEW_LINE INDENT count [ i ] = 0 NEW_LINE DEDENT length = len ( N ) NEW_LINE for i in range ( 0 , length ) : NEW_LINE INDENT count [ int ( N [ i ] ) ] += 1 NEW_LINE DEDENT result = factorial [ int ( length ) ] NEW_LINE for i in range ( 0 , 10 ) : NEW_LINE INDENT result = ( result * modInverse ( factorial [ int ( count [ i ] ) ] , m ) ) % m NEW_LINE DEDENT print ( result ) NEW_LINE DEDENT N = "0223" ; NEW_LINE countNumbers ( N ) NEW_LINE