Bit Strings

#include <iostream>

using namespace std;

int d[1010101];
const int P = (1e9)+7;

int main() {
		d[0] = 1;
		int n, k;
		cin >> n >> k;
		for (int i = 1; i <= n; i++) {
				if (i < k) d[i] = (1<<i)%P;
				else if (i == k) d[i] = ((1<<i)-1)%P;
				else d[i] = (d[i-1]*2 % P - d[i-k-1] % P) % P;
		}
		cout << d[n] << endl;
}

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: WRONG ANSWER

Test 12

Verdict: ACCEPTED

Test 13

Verdict: WRONG ANSWER

Test 14

Verdict: WRONG ANSWER

Test 15

Verdict: WRONG ANSWER

Test 16

Verdict: WRONG ANSWER

Test 17

Verdict: WRONG ANSWER

Test 18

Verdict: WRONG ANSWER