Given an integer N, the task is to find the number of binary strings of size 2*N in which each prefix of the string has more than or an equal number of 1's than 0's.
Note: The answer can be very large. So, output answer modulo 10^{9}+7
Example 1:
Input: N = 2
Output: 2
Explanation: 1100, 1010 are two 
such strings of size 4
Example 2:
Input: N = 3
Output: 5
Explanation: 111000 101100 101010 110010 
110100 are such 5 strings
Your Task:  
You don't need to read input or print anything. Complete the function prefixStrings() which takes N as input parameter and returns an integer value.
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:
	def prefixStrings(self, N):
		# code here

Solutions:
import math

class Solution:

	def prefixStrings(self, N):
		dp = [0 for i in range(N + 1)]
		(dp[0], dp[1]) = (1, 1)
		mod = 1000000007
		for i in range(2, N + 1):
			for j in range(0, i):
				dp[i] += dp[j] * dp[i - j - 1] % mod
		return dp[N] % mod


class Solution:

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


from functools import lru_cache

class Solution:

	def prefixStrings(self, n):
		mod = 1000000007
		f = [0] * (2 * n + 1)
		f[1] = 1
		for i in range(2, 2 * n + 1):
			f[i] = i * f[i - 1]
		return f[2 * n] // (f[n] * f[n + 1]) % mod


def catalan(n):
	if n == 0 or n == 1:
		return 1
	catalan = [0] * (n + 1)
	catalan[0] = 1
	catalan[1] = 1
	for i in range(2, n + 1):
		for j in range(i):
			catalan[i] += catalan[j] * catalan[i - j - 1]
		catalan[i] = catalan[i] % 1000000007
	return catalan[n]

class Solution:

	def prefixStrings(self, N):
		return catalan(N)


class Solution:

	def prefixStrings(self, N):
		a = [0 for hm in range(N + 1)]
		for hm in range(N + 1):
			if hm < 2:
				a[hm] = 1
			else:
				for gm in range(hm):
					a[hm] += a[gm] * a[hm - gm - 1]
		return a[N] % (10 ** 9 + 7)


class Solution:

	def prefixStrings(self, N):
		arr = [0] * (N + 1)
		arr[0] = arr[1] = 1
		for i in range(2, N + 1):
			for j in range(i):
				arr[i] += arr[j] * arr[i - j - 1]
		return arr[N] % 1000000007


class Solution:

	def prefixStrings(self, N):
		catalan = [1 for i in range(N + 1)]
		for i in range(2, N + 1):
			catalan[i] = 0
			for j in range(i):
				catalan[i] += catalan[j] * catalan[i - 1 - j] % (10 ** 9 + 7)
		return catalan[N] % (10 ** 9 + 7)


class Solution:

	def fact(self, n):
		if n == 0 or n == 1:
			return 1
		dp = [1] * (n + 1)
		for i in range(2, n + 1):
			dp[i] = dp[i - 1] * i
		return dp[n]

	def prefixStrings(self, N):
		string_size = N * 2
		if N == 0:
			return 0
		if N == 1:
			return 1
		x = self.fact(2 * N)
		y = self.fact(N) * self.fact(N)
		z = x // y // (N + 1)
		return z % 1000000007


class Solution:

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


class Solution:

	def prefixStrings(self, N):
		catalan = [0] * (N + 1)
		catalan[0] = 1
		catalan[1] = 1
		for i in range(2, N + 1):
			for j in range(i):
				catalan[i] += catalan[j] * catalan[i - j - 1]
		return catalan[N] % 1000000007
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.prefixStrings(N)
		print(ans)


import sys
sys.setrecursionlimit(10 ** 5)
from functools import lru_cache

class Solution:

	@lru_cache(None)
	def prefixStrings(self, N):
		MOD = 1000000007
		if N <= 1:
			return 1
		ans = 0
		for i in range(N):
			ans += self.prefixStrings(i) * self.prefixStrings(N - i - 1)
		return ans % MOD
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.prefixStrings(N)
		print(ans)


class Solution:

	def prefixStrings(self, N):
		dp = [0 for i in range(N + 1)]
		m = 10 ** 9 + 7
		dp[0] = 1
		for i in range(1, N + 1):
			for j in range(i):
				dp[i] = (dp[i] + dp[j] * dp[i - j - 1] % m) % m
		return dp[N]


class Solution:

	def prefixStrings(self, n):
		if n == 0 or n == 1:
			return 1
		catalan = [0] * (n + 1)
		catalan[0] = 1
		catalan[1] = 1
		for i in range(2, n + 1):
			for j in range(i):
				catalan[i] += catalan[j] * catalan[i - j - 1]
		return catalan[n] % (10 ** 9 + 7)


class Solution:

	def binom(self, n, k):
		if k > n - k:
			k = n - k
		res = 1
		for i in range(k):
			res = res * (n - i)
			res = res // (i + 1)
		return res

	def prefixStrings(self, N):
		res = self.binom(2 * N, N)
		res = res // (N + 1)
		return res % 1000000007


class Solution:

	def prefixStrings(self, N):
		C = [1, 1]
		m = 10 ** 9 + 7
		if N >= 2:
			for j in range(2, N + 1):
				val = 0
				for i in range(0, j):
					val = (val + C[i] * C[j - 1 - i]) % m
				C.append(val)
			return int(C[N])
		else:
			return int(C[N])


class Solution:

	def prefixStrings(self, N):
		M = 1000000007
		cn = []
		cn.append(1)
		cn.append(1)
		for i in range(2, N + 1):
			temp = 0
			for j in range(0, i):
				temp += cn[j] % M * (cn[i - j - 1] % M) % M
			cn.append(temp)
		return int(cn[N] % M)


class Solution:

	def prefixStrings(self, N):
		dp = [0 for x in range(N + 1)]
		dp[0] = 1
		dp[1] = 1
		for i in range(2, N + 1):
			for j in range(i):
				dp[i] += dp[j] * dp[i - j - 1]
		return dp[N] % 1000000007


class Solution:

	def prefixStrings(self, N):
		mod = 1000000007
		arr = [1] * (N + 1)
		for i in range(2, N + 1):
			count = 0
			k = i - 1
			j = 0
			while k >= 0:
				count += arr[k] * arr[j] % mod
				k -= 1
				j += 1
			arr[i] = count
		return arr[-1] % mod


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def prefixStrings(self, N):
		memo = {}

		def catalan(n):
			if n in memo:
				return memo[n]
			if n <= 1:
				return 1
			res = 0
			for i in range(n):
				res += catalan(i) * catalan(n - i - 1)
			memo[n] = res
			return memo[n] % 1000000007
		return catalan(N)


class Solution:

	def prefixStrings(self, N):
		mod = 1000000007
		dp = [0 for _ in range(N + 1)]
		dp[0] = 1
		dp[1] = 1
		for i in range(2, N + 1):
			low = 0
			high = i - 1
			while low <= i - 1:
				dp[i] = int((dp[i] + dp[low] * dp[high]) % mod)
				low += 1
				high -= 1
		return int(dp[N] % mod)


import math

class Solution:

	def prefixStrings(self, n):
		mod = 10 ** 9 + 7
		dp = [0] * (1 + n)
		dp[0] = dp[1] = 1
		for i in range(2, n + 1):
			for j in range(i):
				dp[i] += dp[j] % mod * dp[i - j - 1] % mod % mod
		return int(dp[-1] % mod)


class Solution:

	def fact(self, N, M):
		ans = 1
		for i in range(1, N + 1):
			ans = ans * i % M
		return ans

	def prefixStrings(self, N):
		M = 10 ** 9 + 7
		return self.fact(2 * N, M) * pow(self.fact(N, M) ** 2 * (N + 1), M - 2, M) % M


class Solution:

	def binomialCoefficient(self, n, k):
		if k > n - k:
			k = n - k
		res = 1
		for i in range(k):
			res = res * (n - i)
			res = res // (i + 1)
		return res

	def prefixStrings(self, n):
		mod = 1000000007
		x = self.binomialCoefficient(2 * n, n) - self.binomialCoefficient(2 * n, n - 1)
		x = x % mod
		return x


class Solution:

	def prefixStrings(self, n):
		mod = 1000000007
		dp = [0] * (n + 1)
		dp[0] = 1
		dp[1] = 1
		for i in range(2, n + 1):
			for j in range(i):
				dp[i] += dp[j] % mod * (dp[i - j - 1] % mod) % mod
		return dp[n] % mod


class Solution:

	def prefixStrings(self, N):
		import sys
		sys.setrecursionlimit(15000000)
		dp = [-1] * (N + 1)

		def cat(n):
			if n == 0:
				return 1
			else:
				c = 0
				for x in range(n):
					if dp[x] == -1:
						dp[x] = cat(x)
					if dp[n - 1 - x] == -1:
						dp[n - 1 - x] = cat(n - 1 - x)
					c = c + dp[x] * dp[n - 1 - x]
				return c
		return cat(N) % (10 ** 9 + 7)


class Solution:

	def prefixStrings(self, N):
		if N <= 1:
			return 1
		dp = [0 for i in range(N + 1)]
		dp[0] = dp[1] = 1
		for i in range(2, N + 1):
			for j in range(i):
				dp[i] += dp[j] * dp[i - j - 1] % (pow(10, 9) + 7)
		return dp[N] % (pow(10, 9) + 7)


class Solution:

	def prefixStrings(self, N):
		t = [1 if i <= 1 else 0 for i in range(N + 1)]
		for i in range(2, N + 1):
			for j in range(i):
				t[i] += t[j] * t[i - j - 1]
		return t[N] % (10 ** 9 + 7)


class Solution:

	def prefixStrings(self, N):
		cat = 1
		for i in range(1, N + 1):
			cat *= 4 * i - 2
			cat //= i + 1
		return cat % (10 ** 9 + 7)


class Solution:

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


class Solution:

	def prefixStrings(self, N):
		table = [1, 1]
		for i in range(2, N + 1):
			s = 0
			for j in range(i // 2 + 1):
				if j < i - j - 1:
					s += table[j] * table[i - j - 1] * 2
				elif j == i - j - 1:
					s += table[j] * table[i - j - 1]
					break
				else:
					break
			table.append(s % 1000000007)
		return table[-1]


class Solution:

	def prefixStrings(self, N):
		catalan = [0 for _ in range(N + 1)]
		catalan[0] = catalan[1] = 1
		MOD = int(10 ** 9 + 7)
		for n in range(2, N + 1):
			for i in range(n):
				catalan[n] = int((catalan[n] + int(catalan[i] * catalan[n - 1 - i] % MOD)) % MOD)
		return int(catalan[N] % MOD)


import sys
sys.setrecursionlimit(10 ** 5)

class Solution:

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


class Solution:

	def prefixStrings(self, N):
		self.N = N
		n = N
		fibb = [1, 1]
		while len(fibb) <= n:
			m = len(fibb)
			ans = 0
			for i in range(m):
				ans += fibb[i] * fibb[m - 1 - i]
			fibb.append(ans)
		return fibb[-1] % (10 ** 9 + 7)


class Solution:

	def catalan_number(self, n, k):
		if k > n - k:
			k = n - k
		ans = 1
		for i in range(k):
			ans = ans * (n - i)
			ans = ans // (i + 1)
		return ans

	def prefixStrings(self, n):
		c = self.catalan_number(2 * n, n)
		return c // (n + 1) % (10 ** 9 + 7)


class Solution:

	def prefixStrings(self, N):
		dp = [0] * (N + 1)
		dp[0] = dp[1] = 1
		for k in range(2, N + 1):
			i = 0
			j = k - 1
			while i < N:
				dp[k] += dp[i] * dp[j]
				j -= 1
				i += 1
		return dp[-1] % (10 ** 9 + 7)


class Solution:

	def inverse_mod(self, a, b, M):
		if b == 1:
			return a
		if b == 0:
			return 1
		tmp = self.inverse_mod(a, int(b / 2), M)
		tmp = tmp % M * (tmp % M) % M
		if b % 2:
			tmp = tmp * a % M
		return tmp

	def cal_fact(self, N):
		M = 1000000007
		fact = [1] * (N + 5)
		for i in range(2, N + 5):
			fact[i] = fact[i - 1] * i % M
		return fact

	def prefixStrings(self, N):
		M = 1000000007
		fact = self.cal_fact(2 * N)
		ans = fact[2 * N] * (self.inverse_mod(fact[N], M - 2, M) * self.inverse_mod(fact[N + 1], M - 2, M)) % M
		return ans


class Solution:

	def prefixStrings(self, n):
		mod = 10 ** 9 + 7
		memo = [0 for i in range(n + 1)]
		memo[0] = 1
		for i in range(1, n + 1):
			for j in range(i):
				memo[i] = memo[i] + memo[j] * memo[i - 1 - j]
		return memo[n] % mod


class Solution:

	def prefixStrings(self, N):

		def fact(n, r):
			if r > n - r:
				r = n - r
			res = 1
			for i in range(r):
				res *= n - i
				res //= i + 1
			return res

		def catalan(n):
			c = fact(2 * n, n)
			return c // (n + 1)
		return catalan(N) % 1000000007


class Solution:

	def prefixStrings(self, N):
		result = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
		result[-1][-1] = 1
		for i in range(N - 1, -1, -1):
			for j in range(N, i - 1, -1):
				if j < N:
					result[i][j] = result[i][j + 1]
				result[i][j] += result[i + 1][j]
		return result[0][0] % (10 ** 9 + 7)


class Solution:

	def prefixStrings(self, N):
		c = [1, 1, 2]
		if N == 0 or N == 1 or N == 2:
			return c[N]
		for i in range(N - 2):
			s = 0
			l = len(c)
			for j in range(0, l):
				s += c[j] * c[l - 1 - j]
			c.append(s)
		return c[-1] % (10 ** 9 + 7)


def Catlan(n):
	dp = [0 for i in range(n + 1)]
	(dp[0], dp[1]) = (1, 1)
	for i in range(2, n + 1):
		k = i - 1
		for j in range(i):
			dp[i] = (dp[i] + dp[j] * dp[k]) % 1000000007
			k = k - 1
	return dp[-1]

class Solution:

	def prefixStrings(self, N):
		return Catlan(N)


class Solution:

	def prefixStrings(self, N):
		if N == 1:
			return 1
		mod = 10 ** 9 + 7
		ans = [0] * (N + 1)
		ans[0] = ans[1] = 1
		for i in range(2, N + 1):
			for j in range(i):
				ans[i] += ans[j] % mod * (ans[i - j - 1] % mod) % mod
				ans[i] %= mod
		return ans[N]