Given a positive integer N, the task is to find the number of different ways in which N can be written as a sum of two or more positive integers.
Example 1:
Input:
N = 5
Output: 6
Explanation: 
1+1+1+1+1
1+1+1+2
1+1+3
1+4
2+1+2
2+3
So, a total of 6 ways.
Example 2:
Input:
N = 3
Output: 2
Your Task:
Your task is to complete the function countWays() which takes 1 argument(N) and returns the answer%(10^9 + 7).
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N)
Constraints:
1 <= N <= 10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:
    #Function to count the number of different ways in which n can be 
    #written as a sum of two or more positive integers.
    def countWays(self,n):
       
        mod = 1000000007
        # code here

Solutions:
class Solution:

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


class Solution:

	def countWays(self, n):
		mod = 1000000007
		table = [0] * (n + 1)
		table[0] = 1
		for i in range(1, n):
			for j in range(i, n + 1):
				table[j] = table[j] + table[j - i]
		return table[n]


def dynamic(n):
	dp = [0 for _ in range(n + 1)]
	dp[0] = 1
	for i in range(1, n):
		for j in range(i, n + 1):
			dp[j] += dp[j - i]
	return dp[-1] % (10 ** 9 + 7)

class Solution:

	def countWays(self, n):
		return dynamic(n)


from collections import defaultdict

class Solution:

	def countWays(self, n):
		d = defaultdict(lambda : 0)
		d[0] = 1
		for i in range(n - 1, 0, -1):
			temp = defaultdict(lambda : 0)
			for item in d:
				j = i
				while j <= n:
					temp[item + j] += d[item]
					j += i
			for value in temp:
				if value <= n:
					d[value] += temp[value]
		return d[n]


class Solution:

	def countWays(self, n):
		import sys
		sys.setrecursionlimit(10 ** 6)
		mod = 1000000007

		def solve(n, w, wt, dp):
			if w == 0:
				return 1
			if n == 0 or w < 0:
				return 0
			if dp[n][w] != -1:
				return dp[n][w]
			if wt[n - 1] <= w:
				take = solve(n, w - wt[n - 1], wt, dp)
				notake = solve(n - 1, w, wt, dp)
				dp[n][w] = (take % mod + notake % mod) % mod
			else:
				notake = solve(n - 1, w, wt, dp)
				dp[n][w] = notake % mod
			return dp[n][w]
		wt = []
		for i in range(1, n):
			wt.append(i)
		n1 = n - 1
		dp = []
		for i in range(n + 1):
			dp.append([-1] * (n + 1))
		return solve(n1, n, wt, dp) % mod


class Solution:

	def countWays(self, n):
		coins = [i + 1 for i in range(n)]
		g = [0] * (n + 1)
		g[0] = 1
		for i in range(n - 1):
			for j in range(coins[i], n + 1):
				g[j] = (g[j] + g[j - coins[i]]) % 1000000007
		return g[n]


class Solution:

	def solve(self, n, arr, i, dp):
		if n == 0:
			return 1
		if n < 0 or i >= len(arr):
			return 0
		if (i, n) in dp:
			return dp[i, n]
		take = self.solve(n - arr[i], arr, i, dp)
		nottake = self.solve(n, arr, i + 1, dp)
		dp[i, n] = (take + nottake) % (10 ** 9 + 7)
		return dp[i, n]

	def countWays(self, n):
		arr = [i for i in range(1, n)]
		dp = {}
		return self.solve(n, arr, 0, dp)


class Solution:

	def countWays(self, n):
		mod = 1000000007
		possible = []
		for i in range(1, n):
			possible.append(i)
		no_of_ele = len(possible)
		dp = [0] * (n + 1)
		dp[0] = 1
		for i in range(no_of_ele):
			for j in range(n + 1):
				if j - possible[i] >= 0:
					dp[j] = dp[j] + dp[j - possible[i]]
		return dp[n]


class Solution:

	def countWays(self, n):
		mod = 1000000007
		cache = [0] * (n + 1)
		cache[0] = 1
		for coin in range(n):
			for index in range(n + 1):
				if index - coin >= 0:
					cache[index] += cache[index - coin]
		return cache[n] // 2


class Solution:

	def countWays(self, n):
		if n == 1:
			return 0
		mod = 1000000007
		coins = [i for i in range(1, n)]
		dp = [[0 for i in range(n - 1)] for j in range(n + 1)]
		for i in range(n - 1):
			dp[0][i] = 1
		for i in range(1, n + 1):
			for j in range(n - 1):
				take = dp[i - coins[j]][j] if i - coins[j] >= 0 else 0
				nottake = dp[i][j - 1] if j >= 1 else 0
				dp[i][j] = take + nottake
		return dp[n][n - 2]


class Solution:

	def countWays(self, n):
		mod = 1000000007
		dp = [0 for i in range(n + 1)]
		dp[0] = 1
		for i in range(1, n):
			for j in range(i, n + 1):
				dp[j] += dp[j - i]
		return dp[n]
import atexit
import io
import sys
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		n = int(input())
		ob = Solution()
		print(ob.countWays(n))


class Solution:

	def countWays(self, n):
		a = []
		if n == 1:
			return 0
		for i in range(1, n):
			a.append(i)
		m = len(a)
		target = n

		def check(i, j):
			if j == 0:
				return 1
			if i == 0:
				return 1
			if dp[i][j] != -1:
				return dp[i][j]
			take = 0
			if a[i] <= j:
				take = check(i, j - a[i])
			nottake = check(i - 1, j)
			dp[i][j] = take + nottake
			return dp[i][j]
		dp = [[-1 for i in range(target + 1)] for i in range(m)]
		m1 = check(m - 1, target)
		return m1 % 1000000007
import atexit
import io
import sys
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		n = int(input())
		ob = Solution()
		print(ob.countWays(n))


class Solution:

	def countWays(self, n):
		mod = 1000000007
		sum1 = n
		arr = []
		for i in range(1, n):
			arr.append(i)
		n1 = len(arr)
		mat = []
		for i in range(0, n1 + 1):
			l = [99999] * (sum1 + 1)
			mat.append(l)
		mat[0][0] = 1
		for i in range(1, sum1 + 1):
			mat[0][i] = 0
		for i in range(1, n1 + 1):
			mat[i][0] = 1
		for i in range(1, n1 + 1):
			for j in range(1, sum1 + 1):
				if j - arr[i - 1] < 0:
					mat[i][j] = mat[i - 1][j]
				elif mat[i][j - arr[i - 1]] != 99999:
					mat[i][j] = mat[i - 1][j] + mat[i][j - arr[i - 1]]
				else:
					mat[i][j] = mat[i - 1][j]
		if mat[n1][sum1] == 99999:
			return 'Not Possible'
		return mat[n1][sum1] % mod


class Solution:

	def countWays(self, n):
		if n < 2:
			return 0
		l = [0] * (n + 1)
		l[0] = 1
		for i in range(1, n):
			for j in range(1, n + 1):
				if j - i >= 0:
					l[j] += l[j - i]
		return l[n]


class Solution:

	def countWays(self, n):
		mod = 1000000007
		N = n

		def f(n, prev):
			if n == 0:
				return 1
			if (n, prev) in dp:
				return dp[n, prev]
			ans = 0
			for i in range(prev, N):
				if i <= n:
					ans += f(n - i, i)
			dp[n, prev] = ans % mod
			return dp[n, prev]
		dp = {}
		return f(n, 1) % mod


class Solution:

	def countWays(self, n):
		mod = 1000000007
		trackTable = [0] * (n + 1)
		trackTable[0] = 1
		for s in range(1, n + 1):
			for i in range(s, n + 1):
				trackTable[i] += trackTable[i - s]
		return (trackTable[n] - 1) % mod


class Solution:

	def perfectSum(self, arr, n, s):
		arr.sort(reverse=True)
		t = [[None for i in range(s + 1)] for i in range(n + 1)]
		for i in range(n + 1):
			for j in range(s + 1):
				if i == 0:
					t[i][j] = 0
				elif j == 0:
					t[i][j] = 1
		for i in range(1, n + 1):
			for j in range(1, s + 1):
				if arr[i - 1] <= j:
					t[i][j] = t[i][j - arr[i - 1]] + t[i - 1][j]
				else:
					t[i][j] = t[i - 1][j]
		return t[n][s]

	def countWays(self, n):
		arr = [i for i in range(1, n)]
		temp = self.perfectSum(arr, len(arr), n)
		return temp


class Solution:

	def countWays(self, n):
		mod = 1000000007
		arr = []
		for i in range(1, n):
			arr.append(i)
		dp = []
		for _ in range(n + 1):
			dp.append([0] * n)
		for i in range(n):
			dp[0][i] = 1
		for i in range(1, n + 1):
			dp[i][0] = 0
		for i in range(1, n + 1):
			for j in range(1, n):
				dp[i][j] = dp[i][j - 1]
				if arr[j - 1] <= i:
					dp[i][j] += dp[i - arr[j - 1]][j]
		return dp[n][n - 1]


class Solution:

	def countWays(self, n):
		if n < 2:
			return 0
		S = [i for i in range(1, n)]
		m = len(S)
		if n == 0:
			return 1
		prev = [0] * (n + 1)
		temp = [0] * (n + 1)
		temp[0] = 1
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if S[i - 1] <= j:
					temp[j] = temp[j - S[i - 1]] + prev[j]
				else:
					temp[j] = prev[j]
			prev = temp
		return temp[n]


class Solution:

	def countWays(self, n):
		if n < 2:
			return 0

		def f(index, arr, n, dp):
			if index < 0 or n < 0:
				return 0
			if n == 0:
				return 1
			if dp[index][n] != -1:
				return dp[index][n]
			pick = f(index, arr, n - arr[index], dp)
			notpick = f(index - 1, arr, n, dp)
			dp[index][n] = pick + notpick
			return dp[index][n]
		S = [i for i in range(1, n)]
		m = len(S)
		dp = [[-1 for i in range(n + 1)] for j in range(m + 1)]
		return f(m - 1, S, n, dp)


class Solution:

	def countWays(self, n):
		memo = [0 for _ in range(n + 1)]
		memo[0] = 1
		for coin in range(1, n):
			for value in range(n + 1):
				if coin <= value:
					memo[value] += memo[value - coin]
		return memo[-1]


class Solution:

	def numberOfWays(self, coins, n, val):
		mod = 1000000007
		dp = [[0] * (n + 1) for i in range(val + 1)]
		for i in range(n + 1):
			dp[0][i] = 1
		for i in range(1, val + 1):
			for j in range(1, n + 1):
				dp[i][j] += dp[i][j - 1] % mod
				if coins[j - 1] <= i:
					dp[i][j] += dp[i - coins[j - 1]][j] % mod
		return dp[val][n] % mod

	def countWays(self, n):
		arr = [i for i in range(1, n)]
		return self.numberOfWays(arr, n - 1, n)


class Solution:

	def countWays(self, n):
		table = {}
		for x in range(0, n + 1):
			table[x] = 0
		table[0] = 1
		for i in range(1, n):
			for j in range(i, n + 1):
				table[j] += table[j - i]
		return table[n]


dp = [[-1 for i in range(1005)] for j in range(1005)]

class Solution:

	def numberOfWays(self, coins, n, value):
		if value == 0:
			return 1
		if n == 0:
			return 0
		if dp[value][n] != -1:
			return dp[value][n]
		dp[value][n] = self.numberOfWays(coins, n - 1, value)
		if coins[n - 1] <= value:
			dp[value][n] += self.numberOfWays(coins, n, value - coins[n - 1])
		return dp[value][n]

	def countWays(self, n):
		mod = 1000000007
		l = []
		for i in range(1, n):
			l.append(i)
		val = n
		k = len(l)
		ans = self.numberOfWays(l, k, val)
		return ans


class Solution:

	def countWays(self, n):
		mod = 1000000007
		table = [[0 for i in range(n + 1)] for i in range(n)]
		for i in range(n):
			table[i][0] = 1
		coins = []
		for i in range(n):
			coins.append(i + 1)
		for i in range(1, n + 1):
			for j in range(n):
				if j >= 1:
					y = table[j - 1][i]
				else:
					y = 0
				if i - j >= 0:
					x = table[j][i - j]
				else:
					x = 0
				table[j][i] = x + y
		return table[n - 1][n]


class Solution:

	def countWays(self, n):
		mod = 1000000007
		aux_array = [[0 for _ in range(n + 1)] for _ in range(n)]
		for i in range(n):
			aux_array[i][0] = 1
		for i in range(1, n):
			for j in range(1, n + 1):
				aux_array[i][j] = aux_array[i - 1][j]
				if j - i >= 0:
					aux_array[i][j] += aux_array[i][j - i]
		return aux_array[n - 1][n] % mod


class Solution:

	def solve(self, arr, N, n):
		global a
		if N == 0:
			return 1
		if n == 0:
			return 0
		if a[N][n] != -1:
			return a[N][n]
		if N >= arr[n - 1]:
			a[N][n] = self.solve(arr, N - arr[n - 1], n) + self.solve(arr, N, n - 1)
			return a[N][n]
		else:
			a[N][n] = self.solve(arr, N, n - 1)
			return a[N][n]

	def countWays(self, N):
		global a
		mod = 1000000007
		a = []
		arr = []
		for i in range(1, N):
			arr.append(i)
		for i in range(N + 1):
			col = []
			for j in range(len(arr) + 1):
				col.append(-1)
			a.append(col)
		return self.solve(arr, N, len(arr)) % mod


from functools import lru_cache

class Solution:

	def countWays(self, n):
		mod = 1000000007

		@lru_cache(None)
		def dfs(amount, i):
			if amount < 0 or i >= n:
				return 0
			if amount == 0:
				return 1
			ways = dfs(amount - i, i) + dfs(amount, i + 1)
			return ways
		return dfs(n, 1) % mod


class Solution:

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