Find sum of xor of all unordered triplets of the array | Iterative Function to calculate ( x ^ y ) % p in O ( log y ) ; Initialize result ; Update x if it is more than or equal to p ; If y is odd , multiply x with result ; y must be even now y = y >> 1 y = y / 2 ; Returns n ^ ( - 1 ) mod p ; Returns nCr % p using Fermat 's little theorem. ; Base case ; Fill factorial array so that we can find all factorial of r , n and n - r ; Function returns sum of xor of all unordered triplets of the array ; Iterating over the bits ; Number of elements whith k 'th bit  1 and 0 respectively ; Checking if k 'th bit is 1 ; Adding this bit 's part to the answer ; Drivers code
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 x = ( x * x ) % p NEW_LINE DEDENT return res NEW_LINE DEDENT def modInverse ( n , p ) : NEW_LINE INDENT return power ( n , p - 2 , p ) NEW_LINE DEDENT def nCrModPFermat ( n , r , p ) : NEW_LINE INDENT if ( r == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( n < r ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT fac = [ 0 ] * ( n + 1 ) NEW_LINE fac [ 0 ] = 1 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT fac [ i ] = fac [ i - 1 ] * i % p NEW_LINE DEDENT return ( fac [ n ] * modInverse ( fac [ r ] , p ) % p * modInverse ( fac [ n - r ] , p ) % p ) % p NEW_LINE DEDENT def SumOfXor ( a , n ) : NEW_LINE INDENT mod = 10037 NEW_LINE answer = 0 NEW_LINE for k in range ( 32 ) : NEW_LINE INDENT x = 0 NEW_LINE y = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( a [ i ] & ( 1 << k ) ) : NEW_LINE INDENT x += 1 NEW_LINE DEDENT else : NEW_LINE INDENT y += 1 NEW_LINE DEDENT DEDENT answer += ( ( 1 << k ) % mod * ( nCrModPFermat ( x , 3 , mod ) + x * nCrModPFermat ( y , 2 , mod ) ) % mod ) % mod NEW_LINE DEDENT return answer NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 5 NEW_LINE A = [ 3 , 5 , 2 , 18 , 7 ] NEW_LINE print ( SumOfXor ( A , n ) ) NEW_LINE DEDENT