Count sequences of positive integers having product X | Python3 program for the above approach ; Function to prthe total number of possible sequences with product X ; Precomputation of binomial coefficients ; Max length of a subsequence ; Ways dp array ; Fill i slots using all the primes ; Subtract ways for all slots that exactly fill less than i slots ; Total possible sequences ; Print the resultant count ; Driver Code ; Function call
bin = [ [ 0 for i in range ( 3000 ) ] for i in range ( 3000 ) ] NEW_LINE def countWays ( arr ) : NEW_LINE INDENT mod = 10 ** 9 + 7 NEW_LINE bin [ 0 ] [ 0 ] = 1 NEW_LINE for i in range ( 1 , 3000 ) : NEW_LINE INDENT bin [ i ] [ 0 ] = 1 NEW_LINE for j in range ( 1 , i + 1 ) : NEW_LINE INDENT bin [ i ] [ j ] = ( bin [ i - 1 ] [ j ] + bin [ i - 1 ] [ j - 1 ] ) % mod NEW_LINE DEDENT DEDENT n = 0 NEW_LINE for x in arr : NEW_LINE INDENT n += x NEW_LINE DEDENT ways = [ 0 ] * ( n + 1 ) NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT ways [ i ] = 1 NEW_LINE for j in range ( len ( arr ) ) : NEW_LINE INDENT ways [ i ] = ( ways [ i ] * bin [ arr [ j ] + i - 1 ] [ i - 1 ] ) % mod NEW_LINE DEDENT for j in range ( 1 , i ) : NEW_LINE INDENT ways [ i ] = ( ( ways [ i ] - bin [ i ] [ j ] * ways [ j ] ) % mod + mod ) % mod NEW_LINE DEDENT DEDENT ans = 0 NEW_LINE for x in ways : NEW_LINE INDENT ans = ( ans + x ) % mod NEW_LINE DEDENT print ( ans ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 1 ] NEW_LINE countWays ( arr ) NEW_LINE DEDENT