Product of all Subsequences of size K except the minimum and maximum Elements | Python 3 program to find product of all Subsequences of size K except the minimum and maximum Elements ; 2D array to store value of combinations nCr ; Function to pre - calculate value of all combinations nCr ; Function to calculate product of all subsequences except the minimum and maximum elements ; Sorting array so that it becomes easy to calculate the number of times an element will come in first or last place ; An element will occur ' powa ' times in total of which ' powla ' times it will be last element and ' powfa ' times it will be first element ; In total it will come powe = powa - powla - powfa times ; Multiplying a [ i ] powe times using Fermat Little Theorem under MODulo MOD for fast exponentiation ; Driver Code ; pre - calculation of all combinations
MOD = 1000000007 NEW_LINE max = 101 NEW_LINE C = [ [ 0 for i in range ( max ) ] for j in range ( max ) ] NEW_LINE def power ( x , y ) : NEW_LINE INDENT res = 1 NEW_LINE x = x % MOD NEW_LINE while ( y > 0 ) : NEW_LINE INDENT if ( y & 1 ) : NEW_LINE INDENT res = ( res * x ) % MOD NEW_LINE DEDENT y = y >> 1 NEW_LINE x = ( x * x ) % MOD NEW_LINE DEDENT return res % MOD NEW_LINE DEDENT def combi ( n , k ) : NEW_LINE INDENT for i in range ( n + 1 ) : NEW_LINE INDENT for j in range ( min ( i , k ) + 1 ) : NEW_LINE INDENT if ( j == 0 or j == i ) : NEW_LINE INDENT C [ i ] [ j ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT C [ i ] [ j ] = ( C [ i - 1 ] [ j - 1 ] % MOD + C [ i - 1 ] [ j ] % MOD ) % MOD NEW_LINE DEDENT DEDENT DEDENT DEDENT def product ( a , n , k ) : NEW_LINE INDENT ans = 1 NEW_LINE a . sort ( reverse = False ) NEW_LINE powa = C [ n - 1 ] [ k - 1 ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT powla = C [ i ] [ k - 1 ] NEW_LINE powfa = C [ n - i - 1 ] [ k - 1 ] NEW_LINE powe = ( ( powa % MOD ) - ( powla + powfa ) % MOD + MOD ) % MOD NEW_LINE mul = power ( a [ i ] , powe ) % MOD NEW_LINE ans = ( ( ans % MOD ) * ( mul % MOD ) ) % MOD NEW_LINE DEDENT return ans % MOD NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT combi ( 100 , 100 ) NEW_LINE arr = [ 1 , 2 , 3 , 4 ] NEW_LINE n = len ( arr ) NEW_LINE k = 3 NEW_LINE ans = product ( arr , n , k ) NEW_LINE print ( ans ) NEW_LINE DEDENT