Find product of all elements at indexes which are factors of M for all possible sorted subsequences of length M | Python3 program to find the product of all the combinations of M elements from an array whose index in the sorted order divides M completely ; Iterative Function to calculate ( x ^ y ) % p in O ( log y ) ; If y is odd , multiply x with result ; y must be even now ; Iterative Function to calculate ( nCr ) % p and save in f [ n ] [ r ] C ( n , r ) % p = [ C ( n - 1 , r - 1 ) % p + C ( n - 1 , r ) % p ] % p and C ( n , 0 ) = C ( n , n ) = 1 ; If j > i then C ( i , j ) = 0 ; If i is equal to j then C ( i , j ) = 1 ; C ( i , j ) = ( C ( i - 1 , j ) + C ( i - 1 , j - 1 ) ) % p ; Initialize the answer ; For every element arr [ i ] , x is count of occurrence of arr [ i ] in different set such that index of arr [ i ] in those sets divides m completely . ; Finding the count of arr [ i ] by placing it at the index which divides m completely ; Using fermat 's little theorem ; Multiplying with the count ; Driver code
m = 4 NEW_LINE def power ( x , y , p ) : NEW_LINE INDENT res = 1 NEW_LINE x = x % p NEW_LINE while ( y > 0 ) : NEW_LINE INDENT if ( y & 1 ) : NEW_LINE INDENT res = ( res * x ) % p NEW_LINE DEDENT y = y >> 1 NEW_LINE x = ( x * x ) % p NEW_LINE DEDENT return res NEW_LINE DEDENT def nCr ( n , p , f ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT for j in range ( m + 1 ) : NEW_LINE INDENT if ( j > i ) : NEW_LINE INDENT f [ i ] [ j ] = 0 NEW_LINE DEDENT elif ( j == 0 or j == i ) : NEW_LINE INDENT f [ i ] [ j ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT f [ i ] [ j ] = ( ( f [ i - 1 ] [ j ] + f [ i - 1 ] [ j - 1 ] ) % p ) NEW_LINE DEDENT DEDENT DEDENT DEDENT def operations ( arr , n , f ) : NEW_LINE INDENT p = 1000000007 NEW_LINE nCr ( n , p - 1 , f ) NEW_LINE arr . sort ( ) NEW_LINE ans = 1 NEW_LINE for i in range ( n ) : NEW_LINE INDENT x = 0 NEW_LINE for j in range ( 1 , m + 1 ) : NEW_LINE INDENT if ( m % j == 0 ) : NEW_LINE INDENT x = ( ( x + ( f [ n - i - 1 ] [ m - j ] * f [ i ] [ j - 1 ] ) % ( p - 1 ) ) % ( p - 1 ) ) NEW_LINE DEDENT DEDENT ans = ( ( ans * power ( arr [ i ] , x , p ) ) % p ) NEW_LINE DEDENT print ( ans ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 4 , 5 , 7 , 9 , 3 ] NEW_LINE n = len ( arr ) NEW_LINE f = [ [ 0 for x in range ( m + 1 ) ] for y in range ( n + 1 ) ] NEW_LINE operations ( arr , n , f ) NEW_LINE DEDENT