title: Count ways to make string with no K consecutive zeroes
body: <p>Given a string of length N that is made of only 0 and 1's.But some positions of string are '?'.It means their we can put 0 or 1.</p>
  
  <p>Now , the problem is we need to count the number of ways to fill these '?' positions such that No K 0's can be put together.</p>
  
  <p>Like say we have String of length N=4 and string be 0??0</p>
  
  <p>And let K=3 then here we can put '0' at only at max one position out of two.So strings are :</p>
  
  <pre><code>0100
  0010
  0110
  </code></pre>
  
  <p>So here answer is 3.Now for given string of length N and K,we need to count number of ways to make this string.</p>
  
  <p>My Approach :</p>
  
  <p>Now am having O(N,K) approach to solve this problem using Dynamic programming in which if we put 0 at ith position than we can put K-1 zeroes in next continous segment of '?' and if we put 1 then we can put K zeroes again.</p>
  
  <p>But N and K can be very large.So is their some better and efficient algorithm ?</p>
  
  <p>Code as mentioned in one of the answers :</p>
  
  <pre><code>int n,k;
  cin&gt;&gt;n&gt;&gt;k;
  string s;
  cin&gt;&gt;s;
  s="#"+s;
  int size=s.length();
  
  vector&lt;long long int&gt;F(size+1);
  F[0]=1;
  for(int i=1;i&lt;=size;i++){
      if(s[i]=='R')
      {
          F[i]=0;
      }       
      else if(s[i]=='L'){
          F[i]=1;
      }
      else{
          for(int j=i-1;j&gt;=i-k;j--){
              if(j&lt;0)
              break;
              F[i]=(F[i]+F[j])%MOD;
          }
      }
  }
  cout&lt;&lt;F[size]&lt;&lt;"\n";
  </code></pre>
  
  <p>Now Its failing for test case thats a bit bigger.But i ran it on abrute force solution and it didnt matched.</p>
  
  <p>Test case : n=73,k=7 and string s = ???L?R?LLL?L?L?L?LLL???L???RL?????LR?L?LLRL??R???L?RL????RL?R??LL??LLLR?R</p>
  
  <p>The answer should be 877905026.But the code is giving 246470268</p>