Bit Strings

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll dp[1515151];
ll acc[1515151];
#define M 1000000007LL

ll modpow(ll x, ll p) {
  if (p == 0) return 1LL%M;
  ll u = modpow(x, p/2);
  u = (u * u) % M;
  if (p % 2) u = (u * x) % M;
  return u;
}

ll n, k;
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin>>n>>k;
  for (int i = 1; i <= k-1; i++) {
    dp[i] = modpow(2, i);
  }
  dp[k] = modpow(2, k)-1;
  dp[k] %= M;
  
  //if (n <= k) cout<<dp[n]<<"\n";
  
  int s = 0;
  ll sm = 0;
  for (int i = 1; i <= k; i++) sm += dp[i];
  for (int i = k+1; i <= 1010101; i++) {
    dp[i] = sm - dp[s];
    dp[i] %= M;
    
    sm += dp[i];
    sm -= dp[s];
    sm %= M;
    if (sm < 0) sm += M;
    s++;
  }
  
  if (dp[n] < 0) dp[n] += M;
  cout<<dp[n]<<"\n";
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED