Given a set of n elements, find number of ways of partitioning it.
 
Example 1:
Input:
N = 2
Output: 2
Explanation:
Let the set be 
{1, 2}:
{ {1}, {2} } { {1, 2} }
 
Example 2:
Input:
N = 3
Output: 5
Your Task:  
You don't need to read input or print anything. Your task is to complete the function bellNumber() which takes the integer N as input parameters and returns the number of ways of partitioning n elements. Since the value can be quite large print the value modulo 10^{9}+7.
Expected Time Complexity: O(N^2)
Expected Auxiliary Space: O(N^2)
 
Constraints:
1 ≤ N ≤ 1000

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Starter code: #User function Template for python3


class Solution:
    def bellNumber (self, N):
        # code here





Solutions:
class Solution:

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


class Solution:

	def bellNumber(self, N):
		a = [[0 for i in range(N)] for j in range(N)]
		a[0][0] = 1
		for i in range(1, N):
			a[i][0] = a[i - 1][i - 1]
			for j in range(1, i + 1):
				a[i][j] = (a[i - 1][j - 1] + a[i][j - 1]) % 1000000007
		return a[N - 1][N - 1] % 1000000007


class Solution:

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


class Solution:

	def bellNumber(self, N):
		if N <= 1:
			return 1
		limit = 1000000007
		p = [1, 1]
		bino = [1, 1]
		for n in range(2, N + 1):
			p_sum = 1
			bino_next = [1]
			for r in range(1, n):
				p_sum += p[r] * bino[r]
				p_sum = p_sum % limit
				bino_next.append((bino[r - 1] + bino[r]) % limit)
			bino_next.append(1)
			p.append(p_sum)
			bino = bino_next
		return p[-1]


class Solution:

	def bellNumber(self, n):
		bell = [[0 for i in range(n + 1)] for j in range(n + 1)]
		bell[0][0] = 1
		for i in range(1, n + 1):
			bell[i][0] = bell[i - 1][i - 1]
			for j in range(1, i + 1):
				bell[i][j] = (bell[i - 1][j - 1] + bell[i][j - 1]) % 1000000007
		return bell[n][0]


class Solution:

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


class Solution:

	def bellNumber(self, N):
		bellTri = [[1 for j in range(N)] for i in range(N)]
		MOD = 10 ** 9 + 7
		i = 1
		while i < N:
			bellTri[i][0] = bellTri[i - 1][i - 1]
			j = 1
			while j <= i:
				bellTri[i][j] = (bellTri[i][j - 1] + bellTri[i - 1][j - 1]) % MOD
				j += 1
			i += 1
		return bellTri[N - 1][N - 1]


class Solution:

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


class Solution:

	def bellNumber(self, n):
		mod = 1000000000.0 + 7
		bell = [[0 for i in range(n + 1)] for j in range(n + 1)]
		bell[0][0] = 1
		for i in range(1, n + 1):
			bell[i][0] = bell[i - 1][i - 1]
			for j in range(1, i + 1):
				bell[i][j] = bell[i - 1][j - 1] % mod + bell[i][j - 1] % mod
		return int(bell[n][0] % mod)


class Solution:

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


class Solution:

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


class Solution:

	def bellNumber(self, N):
		a = [1]
		b = []
		n = N
		i = 0
		j = 0
		while j != n - 1:
			if len(b) == 0:
				b.append(a[-1])
			if b != 0:
				h = len(a)
				while h != 0:
					c = a[i] + b[i]
					b.append(c)
					i += 1
					h -= 1
				a.clear()
				a = b[:]
				b.clear()
			i = 0
			j += 1
		return a[-1] % (10 ** 9 + 7)