Find product of all elements at indexes which are factors of M for all possible sorted subsequences of length M | C # 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
using System ; class GFG { static int m = 4 ; static long power ( long x , long y , long p ) { long res = 1 ; x = x % p ; while ( y > 0 ) { if ( y % 2 == 1 ) res = ( res * x ) % p ; y = y >> 1 ; x = ( x * x ) % p ; } return res ; } static void nCr ( int n , long p , int [ , ] f ) { for ( int i = 0 ; i <= n ; i ++ ) { for ( int j = 0 ; j <= m ; j ++ ) { if ( j > i ) f [ i , j ] = 0 ; else if ( j == 0 j == i ) f [ i , j ] = 1 ; else f [ i , j ] = ( f [ i - 1 , j ] + f [ i - 1 , j - 1 ] ) % ( int ) p ; } } } static void operations ( int [ ] arr , int n , int [ , ] f ) { long p = 1000000007 ; nCr ( n , p - 1 , f ) ; Array . Sort ( arr ) ; long ans = 1 ; for ( int i = 0 ; i < n ; i ++ ) { long x = 0 ; for ( int j = 1 ; j <= m ; j ++ ) { if ( m % j == 0 ) x = ( x + ( f [ n - i - 1 , m - j ] * f [ i , j - 1 ] ) % ( p - 1 ) ) % ( p - 1 ) ; } ans = ( ( ans * power ( arr [ i ] , x , p ) ) % p ) ; } Console . Write ( ans + " STRNEWLINE " ) ; } public static void Main ( String [ ] args ) { int [ ] arr = { 4 , 5 , 7 , 9 , 3 } ; int n = arr . Length ; int [ , ] f = new int [ n + 1 , m + 1 ] ; operations ( arr , n , f ) ; } }