Count of all possible pairs of disjoint subsets of integers from 1 to N | C ++ implementation of the approach ; Modulo exponentiation function ; Function to calculate ( x ^ y ) % p in O ( log ( y ) ) ; Driver function ; Evaluating ( ( 3 ^ n - 2 ^ ( n + 1 ) + 1 ) / 2 ) % p ; From Fermatss little theorem a ^ - 1 ? a ^ ( m - 2 ) ( mod m )
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define p  1000000007 NEW_LINE long long power ( long long x , long long y ) { long long res = 1 ; x = x % p ; while ( y > 0 ) { if ( y & 1 ) res = ( res * x ) % p ; y = y >> 1 ; x = ( x * x ) % p ; } return res % p ; } int main ( ) { long long n = 3 ; long long x = ( power ( 3 , n ) % p + 1 ) % p ; x = ( x - power ( 2 , n + 1 ) + p ) % p ; x = ( x * power ( 2 , p - 2 ) ) % p ; cout << x << " STRNEWLINE " ; }