Count binary strings with twice zeros in first half | pre define some constant ; global values for pre computation ; function to print number of required string ; calculate answer using proposed algorithm ; Driver code
mod = 1000000007 NEW_LINE Max = 1001 NEW_LINE nCr = [ [ 0 for _ in range ( 1003 ) ] for i in range ( 1003 ) ] NEW_LINE def preComputeCoeff ( ) : NEW_LINE INDENT for i in range ( Max ) : NEW_LINE INDENT for j in range ( i + 1 ) : NEW_LINE INDENT if ( j == 0 or j == i ) : NEW_LINE INDENT nCr [ i ] [ j ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT nCr [ i ] [ j ] = ( nCr [ i - 1 ] [ j - 1 ] + nCr [ i - 1 ] [ j ] ) % mod NEW_LINE DEDENT DEDENT DEDENT DEDENT def computeStringCount ( N ) : NEW_LINE INDENT n = N // 2 NEW_LINE ans = 0 NEW_LINE for i in range ( 2 , n + 1 , 2 ) : NEW_LINE INDENT ans = ( ans + ( ( nCr [ n ] [ i ] * nCr [ n ] [ i // 2 ] ) % mod ) ) % mod NEW_LINE DEDENT return ans NEW_LINE DEDENT preComputeCoeff ( ) NEW_LINE N = 3 NEW_LINE print ( computeStringCount ( N ) ) NEW_LINE