Count sequences of positive integers having product X | Javascript program for the above approach ; Function to print the 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
var bin = Array . from ( Array ( 3000 ) , ( ) => Array ( 3000 ) . fill ( 0 ) ) ; function countWays ( arr ) { var mod = 1000000007 ; bin [ 0 ] [ 0 ] = 1 ; for ( var i = 1 ; i < 3000 ; i ++ ) { bin [ i ] [ 0 ] = 1 ; for ( var j = 1 ; j <= i ; j ++ ) { bin [ i ] [ j ] = ( bin [ i - 1 ] [ j ] + bin [ i - 1 ] [ j - 1 ] ) % mod ; } } var n = 0 ; for ( var x = 0 ; x < arr . length ; x ++ ) n += arr [ x ] ; var ways = Array ( n + 1 ) . fill ( 0 ) ; for ( var i = 1 ; i <= n ; i ++ ) { ways [ i ] = 1 ; for ( var j = 0 ; j < arr . length ; j ++ ) { ways [ i ] = ( ways [ i ] * bin [ arr [ j ] + i - 1 ] [ i - 1 ] ) % mod ; } for ( var j = 1 ; j < i ; j ++ ) { ways [ i ] = ( ( ways [ i ] - bin [ i ] [ j ] * ways [ j ] ) % mod + mod ) % mod ; } } var ans = 0 ; for ( var i = 1 ; i <= n ; i ++ ) ans = ( ans + ways [ i ] ) % mod ; document . write ( ans ) ; } var arr = [ 1 , 1 ] ; countWays ( arr ) ;