Sum of sum of all subsets of a set formed by first N natural numbers | Iterative Function to calculate ( x ^ y ) % p in O ( log y ) ; $x = $x % $p ; Update x if it is more than or equal to p ; If y is odd , multiply x with the result ; y must be even now $y = $y >> 1 ; y = y / 2 ; function to find ff ( n ) ; In formula n is starting from zero ; calculate answer using formula 2 ^ n * ( n ^ 2 + n + 2 ) - 1 ; whenever answer is greater than or equals to mod then modulo it . ; adding modulo while subtraction is very necessary otherwise it will cause wrong answer ; Driver code ; function call
< ? php function power ( $ x , $ y , $ p ) { while ( $ y > 0 ) { if ( $ y & 1 ) $ res = ( $ res * $ x ) % $ p ; $ x = ( $ x * $ x ) % $ p ; } return $ res ; } function check ( $ n ) { $ mod = 1e9 + 7 ; $ n -- ; $ ans = $ n * $ n ; if ( $ ans >= $ mod ) $ ans %= $ mod ; $ ans += $ n + 2 ; if ( $ ans >= $ mod ) $ ans %= $ mod ; $ ans = ( power ( 2 , $ n , $ mod ) % $ mod * $ ans % $ mod ) % $ mod ; $ ans = ( $ ans - 1 + $ mod ) % $ mod ; return $ ans ; } $ n = 4 ; echo check ( $ n ) . " STRNEWLINE " ; ? >