Read problems statements in Mandarin Chinese  and Russian. 

------ Sereja and Arrays ------ 

Sereja have an array that consist of n integers a1, a2, ..., an (0 ≤ ai ≤ 1). Sereja can make next operation:  fix some integer i (1 ≤ i ≤ n - k + 1)  

subtract 1 from values: ai, ai + 1, ..., ai + k - 1Sereja call array a good if it is possible to make some operations, that he can and get array that contain only zeros. Now Sereja interested in next question: how many good arrays a with length n exist?

------ Input ------ 
First line contain integer T — number of testcases. T tests follow. Each testcase is given by two integers n and k.

------ Constraints ------ 
$ 1 ≤ T ≤ 10 $ $ 1 ≤ k ≤ n ≤ 105 $ 

------ Output ------ 
For each testcase output answer modulo 109 + 7.

------ Note ------ 

Test #0-1(25 points) n  ≤ 15
Test #2(25 points) n  ≤ 100
Test #3(50 points) n  ≤ 100000

----- Sample Input 1 ------ 
3
3 3
5 2
5 1
----- Sample Output 1 ------ 
2
8
32

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Combinatorics

Mathematics
Skill types: Dynamic programming

Starter code:

Solutions:
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(N, K) = list(map(int, input().split()))
	if N == K:
		print(2)
		continue
	sm = [0] * N
	vals = [0] * N
	for i in range(N):
		if i < K:
			vals[i] = 1
		else:
			vals[i] = (sm[i - K] + 1) % mod
		if i != 0:
			sm[i] = (sm[i - 1] + vals[i]) % mod
		else:
			sm[i] = vals[i] % mod
	print((sm[-K] + 1) % mod)


m = 10 ** 9 + 7

def solve(n, k):
	dp = [1] * k + [0] * (n - k + 1)
	for i in range(k, n + 1):
		dp[i] = (dp[i - 1] + dp[i - k]) % m
	return dp[-1]
for _ in range(int(input())):
	print(solve(*map(int, input().split())))


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	dp = [0] * a
	step = b
	for i in range(a):
		if i - (step - 1) >= 0:
			dp[i] = 1 + dp[i - step]
		if i - 1 >= 0:
			dp[i] += dp[i - 1]
	print(pow(dp[-1] + 1, 1, 10 ** 9 + 7))


def solve(ind, step, size, memo):
	if ind + step > size:
		return 0
	if ind in memo:
		return memo[ind]
	l = 1 + solve(ind + step, step, size, memo) + solve(ind + 1, step, size, memo)
	if ind not in memo:
		memo[ind] = l
	return l

def solve1(ind, step, size):
	if ind - (step - 1) < 0:
		return 0
	l = 1 + solve1(ind - step, step, size) + solve1(ind - 1, step, size)
	return l
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	dp = [0] * a
	step = b
	for i in range(a):
		if i - (step - 1) >= 0:
			dp[i] = 1 + dp[i - step]
		if i - 1 >= 0:
			dp[i] += dp[i - 1]
	print(pow(dp[-1] + 1, 1, 10 ** 9 + 7))


from sys import stdin, stdout
input = stdin.readline
mod = 10 ** 9 + 7
N = 100001
factorialNumInverse = [None] * (N + 1)
naturalNumInverse = [None] * (N + 1)
fact = [None] * (N + 1)

def InverseofNumber(p):
	naturalNumInverse[0] = naturalNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		naturalNumInverse[i] = naturalNumInverse[p % i] * (p - int(p / i)) % p

def InverseofFactorial(p):
	factorialNumInverse[0] = factorialNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		factorialNumInverse[i] = naturalNumInverse[i] * factorialNumInverse[i - 1] % p

def factorial(p):
	fact[0] = 1
	for i in range(1, N + 1):
		fact[i] = fact[i - 1] * i % p

def Binomial(N, R, p):
	if N < R:
		return 0
	ans = fact[N] * factorialNumInverse[R] % p * factorialNumInverse[N - R] % p
	return ans
InverseofNumber(mod)
InverseofFactorial(mod)
factorial(mod)
t = int(input())
for _ in range(t):
	(A, B) = map(int, input().split())
	ans = 0
	for i in range(0, A // B + 1):
		ans += Binomial(A - (B - 1) * i, i, mod)
		ans %= mod
	print(ans)


import sys
sys.setrecursionlimit(500000)
learnedPairs = dict()
testcases = int(input())

def returnValue(pair):
	n = pair[0]
	k = pair[1]
	if pair in learnedPairs:
		return learnedPairs[pair]
	if k == 1:
		learnedPairs[pair] = 2 ** n
		return 2 ** n
	if n < 1 or k < 1 or n < k:
		learnedPairs[pair] = 1
		return 1
	if n == k:
		learnedPairs[pair] = 2
		return 2
	total = 0
	total = total + returnValue((n - 1, k)) + returnValue((n - k, k))
	learnedPairs[pair] = total
	return total
for i in range(testcases):
	pair = tuple(map(int, input().split()))
	print(returnValue(pair) % (10 ** 9 + 7))


import sys
import math
from queue import Queue
import heapq

def main(n, k):
	dp = [0] * (n + 1)
	dp[0] = 1
	mod = 10 ** 9 + 7
	for i in range(1, n + 1):
		if i - k >= 0:
			dp[i] += dp[i - k]
		dp[i] += dp[i - 1]
		dp[i] %= mod
	return dp[-1]
t = int(input())
ans = []
for i in range(t):
	(n, k) = list(map(int, input().split()))
	ans.append(main(n, k))
for e in ans:
	print(e)


import sys
import math
from queue import Queue
import heapq
factorials = [0] * (10 ** 5 + 1)

def factorialMod(n, modulus):
	ans = 1
	factorials[0] = 1
	for i in range(1, n + 1):
		ans = ans * i % modulus
		factorials[i] = ans
	return ans % modulus
factorialMod(10 ** 5, 10 ** 9 + 7)

def nCr(a, b, p=10 ** 9 + 7):
	f = math.factorial
	ans = factorials[int(a)] * pow(factorials[int(a - b)] * factorials[int(b)], p - 2, p)
	return ans % p

def main(n, k):
	ans = 0
	mod = 10 ** 9 + 7
	for i in range(0, n + 1):
		num_1 = i / k
		num_0 = n - i
		if num_1 == int(num_1):
			ans = (ans + int(nCr(num_1 + num_0, num_1, mod)) % mod) % mod
	return ans % mod
t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	print(main(n, k))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	dp = [1] * (n + 1)
	dp[k] = 2
	for i in range(k, n + 1):
		dp[i] = (dp[i - 1] + dp[i - k]) % (10 ** 9 + 7)
	print(dp[n])


import sys
sys.setrecursionlimit(10 ** 6)
m = 10 ** 9 + 7

def answer(n, k, ans):
	if ans[n] != -1:
		pass
	elif n == k:
		ans[n] = 2
	elif n < k:
		ans[n] = 1
	else:
		p1 = answer(n - k, k, ans) % m if n - k >= 0 else 0
		p2 = answer(n - 1, k, ans) % m if n - 1 >= 0 else 0
		ans[n] = (p1 + p2) % m
	return ans[n]
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	ans = [-1 for i in range(100010)]
	ans[0] = 1
	if k == 1:
		print(pow(2, n, m))
	else:
		print(answer(n, k, ans))


ans = []
mod = 10 ** 9 + 7
fac = [1 for i in range(100001)]
f = 1
for i in range(2, 100001):
	f = f * i % mod
	fac[i] = f

def ncr(n, r):
	den = fac[r] * fac[n - r] % mod
	return fac[n] * pow(den, mod - 2, mod) % mod
for t in range(int(input())):
	[n, k] = [int(i) for i in input().split()]
	out = 0
	(a, b) = (n, 0)
	while a >= 0:
		out = (out + ncr(a + b, b)) % mod
		a -= k
		b += 1
	ans.append(str(out))
print('\n'.join(ans))


mod = 10 ** 9 + 7
t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	dp = [1] + [0] * n
	for i in range(k):
		dp[i] = 1
	for i in range(k, n + 1):
		dp[i] = (dp[i - 1] + dp[i - k]) % mod
	print(dp[-1])


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	dp = [0] * (n + 1)
	MOD = 10 ** 9 + 7
	dp[0] = 1
	for i in range(1, n + 1):
		if i - k < 0:
			dp[i] = dp[i - 1]
		else:
			dp[i] = (dp[i - 1] + dp[i - k]) % MOD
	print(dp[n])


test = int(input())
mod = 1000000007
while test:
	str = input()
	str = str.split()
	n = int(str[0])
	k = int(str[1])
	dp = list()
	dp.append(1)
	if k == 1:
		dp.append(2)
	else:
		dp.append(1)
	for i in range(2, n + 2):
		if i - k < 0:
			dp.append(dp[i - 1])
		else:
			dp.append(dp[i - 1] + dp[i - k])
		dp[i] %= mod
	print(int(dp[n]))
	test -= 1


def Solve(n):
	if n == 0:
		return 1
	if n < 0:
		return 0
	if Mem[n] != -1:
		return Mem[n]
	Mem[n] = (Solve(n - 1) + Solve(n - k[0])) % (10 ** 9 + 7)
	return Mem[n]
T = int(input())
for t in range(T):
	(n, k) = map(int, input().split())
	k = [k]
	Mem = [-1] * (n + 1)
	for i in range(1, n + 1):
		Mem[i] = Solve(i)
	print(Mem[n])