Given a floor of size n x m and tiles of size 1 x m. The problem is to count the number of ways to tile the given floor using 1 x m tiles. A tile can either be placed horizontally or vertically.
Both n and m are positive integers and 2 < = m.
 
Example 1 :
Input: n = 2, m = 3
Output: 1
Expanation: There is only one way to tile the
given floor.
Example 2 :
Input: n = 4, m = 4
Output: 2
Explanation: There is two ways to tile the
given floor.One way is to place 1 x 4 size 
of tile vertically and another one is to 
place them horizontally.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function countWays() which takes n and m as input parameter and returns the total ways modulo 10^{9} + 7.
 
Expected Time Complexity: O(n)
Expected Space Complexity: O(n)
 
Constraints:
1 <= n <= 100000
2 <= m <= 100000

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:
	def countWays(self, n, m):
		# Code here

Solutions:
class Solution:

	def countWays(self, n, m):
		dp = [0] * (n + 1)
		for i in range(n + 1):
			if i < m:
				dp[i] = 1
			elif i == m:
				dp[i] = 2
			else:
				dp[i] = (dp[i - 1] + dp[i - m]) % 1000000007
		return dp[n] % 1000000007

		def cw(n, m, md, dp):
			count = 0
			if n == m:
				return 2
			elif n < m:
				return 1
			if dp[n] != -1:
				return dp[n]
			r = cw(n - 1, m, md, dp) % md
			l = cw(n - m, m, md, dp) % md
			ans = (r + l) % md
			dp[n] = ans
			return dp[n]
		return cw(n, m, 1000000007, dp)


class Solution:

	def countWays(self, n, m):
		if n < m:
			return 1
		dp = [0] * (n + 1)
		dp[:m] = [1] * m
		dp[m] = 2
		for i in range(m + 1, n + 1):
			dp[i] = (dp[i - 1] + dp[i - m]) % (10 ** 9 + 7)
		return dp[n]


from collections import defaultdict

class Solution:

	def countWays(self, n, m):
		d = defaultdict(lambda : 0)
		d[0] = 1
		for i in range(1, n + 1):
			d[i] = (d[i - 1] + d[i - m]) % (10 ** 9 + 7)
		return d[n]


class Solution:

	def countWays(self, n, m):
		dp = [0] * (n + 1)
		dp[0] = 1
		for i in range(1, n + 1):
			dp[i] += dp[i - 1]
			if i - m >= 0:
				dp[i] += dp[i - m]
			dp[i] = dp[i] % 1000000007
		return dp[n]


class Solution:

	def countWays(self, n, m):
		if n < m:
			return 1
		elif n == m:
			return 2
		else:
			dp = [None] * (n + 1)
			for i in range(1, n + 1):
				if i < m:
					dp[i] = 1
				elif i == m:
					dp[i] = 2
				else:
					dp[i] = dp[i - 1] + dp[i - m]
		return dp[-1] % 1000000007


class Solution:

	def countWays(self, n, m):
		dp = [0] * (n + 1)
		for i in range(len(dp)):
			if i < m:
				dp[i] = 1
			else:
				dp[i] = dp[i - 1] + dp[i - m]
		mod = 10 ** 9 + 7
		return dp[-1] % mod


class Solution:

	def countWays(self, n, m):
		mod = int(10 ** 9 + 7)
		dp = [0] * (n + 1)
		for i in range(1, n + 1):
			if i == 1 or i < m:
				dp[i] = 1
			elif i > m:
				dp[i] = dp[i - 1] + dp[i - m]
			else:
				dp[i] = 2
		return dp[n] % mod


class Solution:

	def countWays(self, n, m):
		dp = [0] * (n + 1)
		for i in range(1, n + 1):
			if i < m:
				dp[i] = 1
			elif i == m:
				dp[i] = 2
			else:
				dp[i] = dp[i - 1] + dp[i - m]
			dp[i] %= 10 ** 9 + 7
		return dp[-1]
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, m) = input().split()
		n = int(n)
		m = int(m)
		ob = Solution()
		ans = ob.countWays(n, m)
		print(ans)


class Solution:

	def countWays(self, n, m):
		if m > n:
			return 1
		mp = [0 for i in range(n)]
		mp[m - 1] = 2
		i = 0
		while i < m - 1:
			mp[i] = 1
			i += 1
		i = m
		while i < n:
			mp[i] = (mp[i - 1] + mp[i - m]) % (10 ** 9 + 7)
			i += 1
		return mp[-1]
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, m) = input().split()
		n = int(n)
		m = int(m)
		ob = Solution()
		ans = ob.countWays(n, m)
		print(ans)


class Solution:

	def countWays(self, n, m):
		dp = [0] * (n + 1)
		dp[1] = 1
		for i in range(2, n + 1):
			if i < m:
				dp[i] = 1
			elif i == m:
				dp[i] = 2
			else:
				dp[i] = dp[i - 1] + dp[i - m]
				dp[i] = int(dp[i] % (1000000000.0 + 7))
		return dp[n]


class Solution:

	def countWays(self, n, m):
		count = []
		for i in range(n + 2):
			count.append(0)
		count[0] = 0
		for i in range(1, n + 1):
			if i > m:
				count[i] = (count[i - 1] + count[i - m]) % 1000000007
			elif i < m or i == 1:
				count[i] = 1
			else:
				count[i] = 2
		return count[n]


class Solution:

	def countWays(self, n, m):
		if m > n:
			return 1
		data = [0 for i in range(n + 1)]
		data[0] = 1
		for i in range(n + 1):
			if i >= 1:
				data[i] = data[i - 1]
			if i >= m:
				data[i] = data[i - 1] + data[i - m]
		return data[n] % (pow(10, 9) + 7)


class Solution:

	def countWays(self, n, m):
		mod = 1000000000.0 + 7
		if n < m:
			return 1
		dp = [1 for _ in range(n + 1)]
		for i in range(m, n + 1):
			if i >= m:
				dp[i] = int((dp[i - m] + dp[i - 1]) % mod)
		return int(dp[n] % mod)


mod = 10 ** 9 + 7

class Solution:

	def countWays(self, n, m):
		dp = [-1 for i in range(n + 1)]
		for i in range(n + 1):
			if i < m:
				dp[i] = 1
			elif i == m:
				dp[i] = 2
			else:
				ans1 = dp[i - m]
				ans2 = dp[i - 1]
				dp[i] = (ans1 + ans2) % mod
		return dp[n]


class Solution:

	def countWays(self, n, m):
		self.mod = 1000000007
		return self.iterative(n, m)

	def dfs(self, n, m):
		if n == 1 or n == 0:
			return 1
		if n < 0:
			return 0
		return self.dfs(n - 1, m) + self.dfs(n - m, m)

	def iterative(self, n, m):
		f = [1, 1]
		for i in range(2, n + 1):
			if i - m < 0:
				f.append(f[i - 1])
			else:
				f.append((f[i - 1] + f[i - m]) % self.mod)
		return f[n]


class Solution:

	def countWays(self, n, m):
		DP = [1 for x in range(n + 1)]
		if m > n:
			return 1
		DP[m] = 2
		for x in range(m + 1, n + 1):
			DP[x] = DP[x - 1] + DP[x - m]
		return DP[n] % (10 ** 9 + 7)


class Solution:

	def countWays(self, n, m):
		arr = [1] * m
		for i in range(n):
			arr.append(arr[-1] + arr[-m])
		return arr[-m] % (10 ** 9 + 7)


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def countWays(self, n, m):
		if n < m:
			return 1
		dp = [0 for i in range(n + 1)]
		for i in range(1, n + 1):
			if m > i:
				dp[i] = 1
			elif m == i:
				dp[i] = 2
			else:
				dp[i] = (dp[i - 1] + dp[i - m]) % (10 ** 9 + 7)
		return dp[-1]