Count of all possible pairs of disjoint subsets of integers from 1 to N | Python3 implementation of the approach ; Modulo exponentiation function ; Function to calculate ( x ^ y ) % p in O ( log ( y ) ) ; Driver Code ; Evaluating ( ( 3 ^ n - 2 ^ ( n + 1 ) + 1 ) / 2 ) % p ; From Fermatss little theorem a ^ - 1 ? a ^ ( m - 2 ) ( mod m )
p = 1000000007 NEW_LINE def power ( x , y ) : 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 % p NEW_LINE DEDENT n = 3 NEW_LINE x = ( power ( 3 , n ) % p + 1 ) % p NEW_LINE x = ( x - power ( 2 , n + 1 ) + p ) % p NEW_LINE x = ( x * power ( 2 , p - 2 ) ) % p NEW_LINE print ( x ) NEW_LINE