Count ways to express even number â €˜ nâ €™ as sum of even integers | Initialize mod variable as constant ; 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 ; Return number of ways to write ' n ' as sum of even integers ; Driver code
< ? php $ MOD = 1000000000.0 ; function power ( $ x , $ y , $ p ) { $ res = 1 ; $ x = $ x % $ p ; while ( $ y > 0 ) { if ( $ y & 1 ) $ res = ( 1 * $ res * $ x ) % $ p ; $ x = ( 1 * $ x * $ x ) % $ p ; } return $ res ; } function countEvenWays ( $ n ) { global $ MOD ; return power ( 2 , $ n / 2 - 1 , $ MOD ) ; } $ n = 6 ; echo countEvenWays ( $ n ) , " STRNEWLINE " ; $ n = 8 ; echo countEvenWays ( $ n ) ; ? >