Function to return no of ways to build a binary string of length N such that 0 s always occur in groups of size K
function noOfBinaryStrings ( $ N , $ k ) { global $ mod ; $ dp = array ( 0 , 100002 , NULL ) ; for ( $ i = 1 ; $ i <= $ k - 1 ; $ i ++ ) { $ dp [ $ i ] = 1 ; } $ dp [ $ k ] = 2 ; for ( $ i = $ k + 1 ; $ i <= $ N ; $ i ++ ) { $ dp [ $ i ] = ( $ dp [ $ i - 1 ] + $ dp [ $ i - $ k ] ) % $ mod ; } return $ dp [ $ N ] ; }