Count sequences of positive integers having product X | C # 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
using System ; class GFG { static int [ , ] bin = new int [ 3000 , 3000 ] ; static void countWays ( int [ ] arr ) { int mod = ( int ) 1e9 + 7 ; bin [ 0 , 0 ] = 1 ; for ( int i = 1 ; i < 3000 ; i ++ ) { bin [ i , 0 ] = 1 ; for ( int j = 1 ; j <= i ; j ++ ) { bin [ i , j ] = ( bin [ i - 1 , j ] + bin [ i - 1 , j - 1 ] ) % mod ; } } int n = 0 ; foreach ( int x in arr ) n += x ; int [ ] ways = new int [ n + 1 ] ; for ( int i = 1 ; i <= n ; i ++ ) { ways [ i ] = 1 ; for ( int j = 0 ; j < arr . Length ; j ++ ) { ways [ i ] = ( ways [ i ] * bin [ arr [ j ] + i - 1 , i - 1 ] ) % mod ; } for ( int j = 1 ; j < i ; j ++ ) { ways [ i ] = ( ( ways [ i ] - bin [ i , j ] * ways [ j ] ) % mod + mod ) % mod ; } } int ans = 0 ; foreach ( int x in ways ) ans = ( ans + x ) % mod ; Console . Write ( ans + " STRNEWLINE " ) ; } public static void Main ( String [ ] args ) { int [ ] arr = { 1 , 1 } ; countWays ( arr ) ; } }