Count total number of even sum sequences | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define M  1000000007 NEW_LINE #define ll  long long int NEW_LINE ll power ( ll x , ll y , ll p ) { ll res = 1 ; x = x % p ; while ( y > 0 ) { if ( y & 1 ) res = ( res * x ) % p ; x = ( x * x ) % p ; } return res ; } ll modInverse ( ll n , ll p ) { return power ( n , p - 2 , p ) ; } ll nCrModPFermat ( ll n , ll r , ll p ) { if ( r == 0 ) return 1 ; ll fac [ n + 1 ] ; fac [ 0 ] = 1 ; for ( ll i = 1 ; i <= n ; i ++ ) fac [ i ] = fac [ i - 1 ] * i % p ; return ( fac [ n ] * modInverse ( fac [ r ] , p ) % p * modInverse ( fac [ n - r ] , p ) % p ) % p ; } ll countOdd ( ll n ) { ll x = n / 2 ; if ( n % 2 == 1 ) x ++ ; return x ; } ll counteEven ( ll n ) { ll x = n / 2 ; return x ; } ll CountEvenSumSequences ( ll n ) { ll count = 0 ; for ( ll i = 0 ; i <= n ; i ++ ) { ll even = i , odd = n - i ; if ( odd % 2 == 1 ) continue ; ll tot = ( power ( countOdd ( n ) , odd , M ) * nCrModPFermat ( n , odd , M ) ) % M ; tot = ( tot * power ( counteEven ( n ) , i , M ) ) % M ; count += tot ; count %= M ; } return count ; } int main ( ) { ll n = 5 ; cout << CountEvenSumSequences ( n ) ; return 0 ; }