Bit Strings

P = int(1e9+7);
d = [1];
n, k = map(int, input().split())

for i in range(1, n+1):
		if i < k:
				d.append(int(2**i)%P)
		elif i == k:
				d.append(int(2**i)-1)
		else:
				d.append((d[i-1]*2%P - d[i-k-1]%P)%P)

print(d[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: TIME LIMIT EXCEEDED

Test 12

Verdict: TIME LIMIT EXCEEDED

Test 13

Verdict: TIME LIMIT EXCEEDED

Test 14

Verdict: TIME LIMIT EXCEEDED

Test 15

Verdict: TIME LIMIT EXCEEDED

Test 16

Verdict: TIME LIMIT EXCEEDED

Test 17

Verdict: TIME LIMIT EXCEEDED

Test 18

Verdict: TIME LIMIT EXCEEDED