Count of N | python 3 program for the above approach ; Find the value of x raised to the yth power modulo MOD ; Stores the value of x ^ y ; Iterate until y is positive ; Function to perform the Modular Multiplicative Inverse using the Fermat 's little theorem ; Modular division x / y , find modular multiplicative inverse of y and multiply by x ; Function to find Binomial Coefficient C ( n , k ) in O ( k ) time ; Base Case ; Update the value of p and q ; Function to find the count of arrays having K as the first element satisfying the given criteria ; Stores the resultant count of arrays ; Find the factorization of K ; Stores the count of the exponent of the currentprime factor ; N is one last prime factor , for c = 1 -> C ( N - 1 + 1 , 1 ) = N ; Return the totol count ; Driver Code
MOD = 1000000007 NEW_LINE from math import sqrt NEW_LINE def modPow ( x , y ) : NEW_LINE INDENT r = 1 NEW_LINE a = x NEW_LINE while ( y > 0 ) : NEW_LINE INDENT if ( ( y & 1 ) == 1 ) : NEW_LINE INDENT r = ( r * a ) % MOD NEW_LINE DEDENT a = ( a * a ) % MOD NEW_LINE y /= 2 NEW_LINE DEDENT return r NEW_LINE DEDENT def modInverse ( x ) : NEW_LINE INDENT return modPow ( x , MOD - 2 ) NEW_LINE DEDENT def modDivision ( p , q ) : NEW_LINE INDENT return ( p * modInverse ( q ) ) % MOD NEW_LINE DEDENT def C ( n , k ) : NEW_LINE INDENT if ( k > n ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT p = 1 NEW_LINE q = 1 NEW_LINE for i in range ( 1 , k + 1 , 1 ) : NEW_LINE INDENT q = ( q * i ) % MOD NEW_LINE p = ( p * ( n - i + 1 ) ) % MOD NEW_LINE DEDENT return modDivision ( p , q ) NEW_LINE DEDENT def countArrays ( N , K ) : NEW_LINE INDENT res = 1 NEW_LINE for p in range ( 2 , int ( sqrt ( K ) ) , 1 ) : NEW_LINE INDENT c = 0 NEW_LINE while ( K % p == 0 ) : NEW_LINE INDENT K /= p NEW_LINE c += 1 NEW_LINE DEDENT res = ( res * C ( N - 1 + c , c ) ) % MOD NEW_LINE DEDENT if ( N > 1 ) : NEW_LINE INDENT res = ( res * N ) % MOD NEW_LINE DEDENT return res NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 3 NEW_LINE K = 5 NEW_LINE print ( countArrays ( N , K ) ) NEW_LINE DEDENT