Given N, count the number of ways to express N as sum of 1, 3 and 4 modulo (10^{9}+7).
 
Example 1:  
Input:
N = 1
Output:
1
Explanation:
There is only one way to represent 1 as
sum of 1,3 and 4. 1 = {1}.
Example 2:  
Input:
N = 3
Output:
2
Explanation:
There is 2 ways to represent 3 as sum
of 1,3 and 4. 3 = {1,1,1}, and 3 = {3}.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function countWays() which takes a Integer N as input and returns the number of ways possible.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
 
Constraints:
1 <= N <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Number theory

Dynamic programming

Starter code: #User function Template for python3



class Solution:

    def countWays(self, N):

        # code here

Solutions:
class Solution:

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


from collections import defaultdict

class Solution:

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


class Solution:

	def countWays(self, N):
		dp = [0 for i in range(N + 1)]
		modValue = 1000000007
		if N <= 2:
			return 1
		dp[0] = 1
		dp[1] = 1
		dp[2] = 1
		dp[3] = 2
		for i in range(4, N + 1):
			dp[i] = (dp[i - 1] + dp[i - 3] + dp[i - 4]) % modValue
		return dp[N]


class Solution:

	def countWays(self, N):
		dp = [0] * (N + 5)
		dp[0] = dp[1] = dp[2] = 1
		dp[3] = 2
		for i in range(4, N + 1):
			dp[i] = (dp[i - 1] + dp[i - 3] + dp[i - 4]) % (10 ** 9 + 7)
		return dp[N] % (10 ** 9 + 7)


class Solution:

	def countWays(self, n):
		k = 10 ** 9 + 7
		arr = [0, 1, 1, 2, 4]
		if n <= 4:
			return arr[n]
		for i in range(5, n + 1):
			arr.append((arr[i - 1] + arr[i - 3] + arr[i - 4]) % k)
		return arr[n]


class Solution:

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


class Solution:

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


class Solution:

	def countWays(self, n):
		if n <= 2:
			return 1
		if n == 3:
			return 2
		dp = [0 for x in range(n + 1)]
		dp[0] = 1
		dp[1] = 1
		dp[2] = 1
		dp[3] = 2
		for i in range(4, n + 1):
			dp[i] = (dp[i - 1] + dp[i - 3] + dp[i - 4]) % 1000000007
		return dp[n]


class Solution:

	def countWays(self, N):
		l = [1, 1, 2, 4]
		for i in range(4, N):
			l.append(l[-1] + l[-3] + l[-4])
			l[-1] = l[-1] % 1000000007
		return l[N - 1] % 1000000007


class Solution:

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


class Solution:

	def countWays(self, N):
		data = [0 for i in range(N + 1)]
		data[0] = 1
		mod = pow(10, 9) + 7
		for i in range(1, N + 1):
			if i >= 4:
				data[i] = data[i - 1] % mod + data[i - 3] % mod + data[i - 4] % mod
			elif i >= 3:
				data[i] = data[i - 1] % mod + data[i - 3] % mod
			else:
				data[i] = data[i - 1] % mod
		return data[N] % mod


class Solution:

	def countWays(self, N):
		dp = [0 for i in range(N + 1)]
		mod = 1000000007
		dp[0] = 1
		dp[1] = 1
		if N > 1:
			dp[2] = 1
		if N > 2:
			dp[3] = 2
		for i in range(4, N + 1):
			dp[i] = (dp[i - 1] % mod + dp[i - 3] % mod + dp[i - 4] % mod) % mod
		return dp[N] % (pow(10, 9) + 7)


import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

	def recur(self, n):
		if n < 0:
			return 0
		if n == 0:
			return 1
		if dp[n]:
			return dp[n]
		dp[n] = (self.recur(n - 1) + self.recur(n - 3) + self.recur(n - 4)) % (10 ** 9 + 7)
		return dp[n]

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


class Solution:

	def countWays(self, N):
		mod = 1000000000.0 + 7
		if N <= 2:
			return 1
		if N == 3:
			return 2
		if N == 4:
			return 3
		dp = [0 for _ in range(N + 1)]
		dp[0] = 0
		dp[1] = 1
		dp[2] = 1
		dp[3] = 2
		dp[4] = 4
		for i in range(5, N + 1):
			dp[i] = int((dp[i - 1] + dp[i - 3] + dp[i - 4]) % mod)
		return dp[N]


class Solution:

	def countWays(self, N):
		n = N
		if n == 1 or n == 2:
			return 1
		if n == 3:
			return 2
		DP = [0 for i in range(0, n + 1)]
		DP[0] = DP[1] = DP[2] = 1
		DP[3] = 2
		for i in range(4, n + 1):
			DP[i] = (DP[i - 1] + DP[i - 3] + DP[i - 4]) % (10 ** 9 + 7)
		return DP[n]


class Solution:

	def countWays(self, n):
		DP = [0] * max(5, n + 1)
		DP[1] = 1
		DP[2] = 1
		DP[3] = 2
		DP[4] = 4
		mod_num = pow(10, 9) + 7
		for i in range(5, n + 1):
			DP[i] = (DP[i - 1] % mod_num + DP[i - 3] % mod_num + DP[i - 4] % mod_num) % mod_num
		return DP[n] % mod_num


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def countWays1(self, N):
		n = N
		DP = [0] * max(5, n + 1)
		DP[1] = 1
		DP[2] = 1
		DP[3] = 2
		DP[4] = 4
		return self.countWaysRec(DP, N)

	def countWaysRec(self, DP, N):
		if DP[N] == 0:
			DP[N] = (self.countWaysRec(DP, N - 1) + self.countWaysRec(DP, N - 3) + self.countWaysRec(DP, N - 4)) % (pow(10, 9) + 7)
		return DP[N]

	def countWays(self, N):
		n = N
		DP = [0] * max(5, n + 1)
		DP[1] = 1
		DP[2] = 1
		DP[3] = 2
		DP[4] = 4
		mod_num = pow(10, 9) + 7
		for i in range(5, n + 1):
			DP[i] = (DP[i - 1] % mod_num + DP[i - 3] % mod_num + DP[i - 4] % mod_num) % mod_num
		return DP[n] % mod_num