Count total number of even sum sequences | Python3 implementation of the approach ; Iterative function to calculate ( x ^ y ) % p in O ( log y ) ; Initialize result ; Update x if it is greater than or equal to p ; If y is odd then multiply x with the result ; y must be even now y = y >> 1 y = y / 2 ; Function to return n ^ ( - 1 ) mod p ; Function to return ( 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 to return the count of odd numbers from 1 to n ; Function to return the count of even numbers from 1 to n ; Function to return the count of the required sequences ; Take i even and n - i odd numbers ; Number of odd numbers must be even ; Total ways of placing n - i odd numbers in the sequence of n numbers ; Add this number to the final answer ; Driver code
M = 1000000007 NEW_LINE 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 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 countOdd ( n ) : NEW_LINE INDENT x = n // 2 NEW_LINE if ( n % 2 == 1 ) : NEW_LINE INDENT x += 1 NEW_LINE DEDENT return x NEW_LINE DEDENT def counteEven ( n ) : NEW_LINE INDENT x = n // 2 NEW_LINE return x NEW_LINE DEDENT def CountEvenSumSequences ( n ) : NEW_LINE INDENT count = 0 NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT even = i NEW_LINE odd = n - i NEW_LINE if ( odd % 2 == 1 ) : NEW_LINE INDENT continue NEW_LINE DEDENT tot = ( power ( countOdd ( n ) , odd , M ) * nCrModPFermat ( n , odd , M ) ) % M NEW_LINE tot = ( tot * power ( counteEven ( n ) , i , M ) ) % M NEW_LINE count += tot NEW_LINE count %= M NEW_LINE DEDENT return count NEW_LINE DEDENT n = 5 NEW_LINE print ( CountEvenSumSequences ( n ) ) NEW_LINE