You are given N balls numbered from 1 to N and there are N baskets numbered from 1 to N in front of you, the i^{th} basket is meant for the i^{th} ball. Calculate the number of ways in which no ball goes into its respective basket.
Example 1:
Input: N = 2
Output: 1
Explanation: The balls are numbered 1 and 2. 
Then there is only one way to dearrange them. 
The (number-basket) pairs will be [(1-2),(2-1)].
Example 2:
Input: 3
Output: 2
Explanation: The (number-basket) pairs are 
[(1-3),(2-1),(3-2)] and [(1-2),(2-3),(3-1)].
Your Task:
You do not need to read input or print anything. Your task is to complete the function disarrange() , which takes the number N as input parameter and returns the number of ways to disarrange them. As the number can be very big return it modulo 10^{9} + 7
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{4}

Source: geeksforgeeks | Difficulty: EASY
Tags: Combinatorics

Starter code: #User function Template for python3



class Solution:

    def disarrange(self, N):

        # code here

Solutions:
class Solution:

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


class Solution:

	def rec_sol(self, N):
		if N == 1:
			return 0
		if N == 2:
			return 1
		return (N - 1) * (self.rec_sol(N - 1) + self.rec_sol(N - 2))

	def dp_sol(self, N):
		if N == 1:
			return 0
		if N == 2:
			return 1
		dp = [0] * (N + 1)
		dp[1] = 0
		dp[2] = 1
		for i in range(3, N + 1):
			dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2])
		return dp[N]

	def disarrange(self, N):
		return self.dp_sol(N) % 1000000007


class Solution:

	def disarrange(self, N):
		stateMap = [0 for i in range(N + 1)]
		stateMap[2] = 1
		for c in range(3, N + 1):
			stateMap[c] = (c - 1) * (stateMap[c - 1] + stateMap[c - 2])
		return stateMap[N] % (10 ** 9 + 7)


class Solution:

	def disarrange(self, N):
		dp1 = 0
		dp2 = 1
		mod = pow(10, 9) + 7
		for i in range(3, N + 1):
			temp = dp2
			dp2 = (i - 1) * (dp1 + dp2) % mod
			dp1 = temp
		return dp2


class Solution:

	def disarrange(self, N):
		dp = [None] * (N + 1)
		dp[0] = 0
		dp[1] = 0
		dp[2] = 1
		mod = pow(10, 9) + 7
		for i in range(3, N + 1):
			dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % mod
		return dp[N]


import sys
sys.setrecursionlimit(10000000)

class Solution:

	def solve(self, N, dp):
		if N == 1:
			return 0
		if N == 2:
			return 1
		if dp[N] != -1:
			return dp[N]
		a = self.solve(N - 1, dp)
		b = self.solve(N - 2, dp)
		ans = (N - 1) * (a + b)
		dp[N] = ans
		return dp[N]

	def disarrange(self, N):
		dp = [-1 for i in range(N + 1)]
		ans = self.solve(N, dp)
		return ans % 1000000007


from sys import stdin, setrecursionlimit
import sys
setrecursionlimit(10 ** 6)

class Solution:

	def solve(self, N, dp):
		if N == 1:
			return 0
		if N == 2:
			return 1
		if dp[N] != -1:
			return dp[N]
		a = self.solve(N - 1, dp)
		b = self.solve(N - 2, dp)
		ans = (N - 1) * (a + b)
		dp[N] = ans
		return dp[N]

	def disarrange(self, N):
		dp = [-1 for i in range(N + 1)]
		ans = self.solve(N, dp)
		return ans % 1000000007


class Solution:

	def disarrange(self, N):
		if N < 3:
			return N - 1
		dp1 = 0
		dp2 = 1
		for i in range(3, N + 1):
			(dp1, dp2) = (dp2, (i - 1) * (dp2 + dp1) % (10 ** 9 + 7))
		return dp2


class Solution:

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


class Solution:

	def disarrange(self, n):
		if n < 4:
			return n - 1
		mod = 1000000007
		(dp1, dp2) = (0, 1)
		for i in range(3, n + 1):
			cur = (i - 1) * (dp1 + dp2) % mod
			dp1 = dp2
			dp2 = cur
		return dp2


mod = 10 ** 9 + 7

class Solution:

	def disarrange(self, N):
		prev2 = 0
		prev1 = 1
		for i in range(3, N + 1):
			ans = (i - 1) * (prev1 + prev2)
			ans = ans % mod
			prev2 = prev1
			prev1 = ans
		return prev1


class Solution:

	def disarrange(self, N):
		mod = 1000000000.0 + 7
		dp = [0] * (N + 1)
		dp[2] = 1
		for i in range(3, N + 1):
			dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % mod
		return int(dp[-1])


class Solution:

	def disarrange(self, n):
		dp = [0] * (n + 1)
		dp[1] = 0
		for i in range(n + 1):
			dp[i] = (i * dp[i - 1] + pow(-1, i)) % 1000000007
		return dp[n]


class Solution:

	def disarrange(self, N):
		prev1 = 0
		prev2 = 1
		Power = pow(10, 9) + 7
		for i in range(3, N + 1):
			temp = prev2
			prev2 = (prev1 + prev2) * (i - 1) % Power
			prev1 = temp
		return prev2


import sys
sys.setrecursionlimit(1 << 30)

class Solution:

	def disarrange(self, N):
		Power = pow(10, 9) + 7
		dp = [-1 for i in range(N + 1)]

		def recursion(N):
			if dp[N] != -1:
				return dp[N]
			if N == 1:
				return 0
			if N == 2:
				return 1
			dp[N] = (recursion(N - 1) + recursion(N - 2)) * (N - 1) % Power
			return dp[N]
		return recursion(N)


mod = 1000000007

class Solution:

	def find(self, N):
		if N == 0:
			return 1
		if N == 1 or N < 0:
			return 0
		return (N - 1) * (self.find(N - 1) + self.find(N - 2)) % mod

	def bottomup(self, N):
		if N == 0:
			return 1
		prev1 = 0
		prev2 = 1
		ans = 0
		for i in range(2, N + 1):
			ans = (i - 1) * (prev1 + prev2) % mod
			prev2 = prev1
			prev1 = ans
		return ans

	def disarrange(self, N):
		return self.bottomup(N)


class Solution:

	def memoization(self, N, dp):
		if N <= 1:
			return 0
		if N == 2:
			return 1
		if dp[N] != -1:
			return dp[N]
		dp[N] = (N - 1) % 1000000007 * (self.memoization(N - 1, dp) % 1000000007 + self.memoization(N - 2, dp) % 1000000007)
		return dp[N]

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

	def disarrange(self, N):
		return self.solveTab(N)


class Solution:

	def disarrange(self, N):
		if N == 1:
			return 0
		if N == 2:
			return 1
		A = [0, 1]
		S = 1
		for i in range(3, N + 1):
			if i % 2 == 1:
				S = A[0] + (i - 2) * S
				A[0] = (i - 1) * S
			else:
				S = A[1] + (i - 2) * S
				A[1] = (i - 1) * S
		return A[(N + 1) % 2] % (10 ** 9 + 7)


class Solution:

	def disarrange(self, n):
		t = [0] * (n + 1)
		t[0] = 0
		t[1] = 0
		t[2] = 1
		for i in range(3, n + 1):
			t[i] = (i - 1) * (t[i - 1] + t[i - 2]) % 1000000007
		return t[n]


class Solution:

	def disarrange(self, N):
		mod = 1000000007
		(prev_1, prev_2) = (0, 1)
		for i in range(3, N + 1):
			temp = prev_2
			prev_2 = (i - 1) * (prev_2 + prev_1) % mod
			prev_1 = temp
		return prev_2


class Solution:

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


def solve(n, dp):
	if n <= 1:
		return 0
	if n == 2:
		return 1
	dp[n] = (n - 1) * (solve(n - 1, dp) + solve(n - 2, dp))
	return dp[n]

class Solution:

	def disarrange(self, n):
		mod = 1000000007
		dp = [0 for _ in range(N + 1)]
		dp[2] = 1
		if n <= 2:
			return dp[n]
		for i in range(3, n + 1):
			dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % mod % mod
		return dp[n]


class Solution:

	def disarrange(self, N):
		dp = [0] * (N + 1)
		dp[1] = 0
		dp[2] = 1
		for i in range(3, N + 1):
			first = dp[i - 1] % 1000000007
			second = dp[i - 2] % 1000000007
			sum = first + second
			ans = (i - 1) * sum % 1000000007
			dp[i] = ans
		return dp[N]


class Solution:

	def disarrange(self, n):
		return self.solvetab(n)

	def solve(self, n, tab):
		if tab[n] != -1:
			return tab[n]
		if n == 0 or n == 1:
			tab[0] = tab[1] = 0
			return tab[n]
		if n == 2:
			tab[n] = 1
			return tab[n]
		else:
			tab[n] = (n - 1) * (self.disarrange(n - 2) + self.disarrange(n - 1))
			return tab[n]

	def solvetab(self, n):
		m = 1000000007
		tab = [-1] * (n + 1)
		tab[0] = tab[1] = 0
		tab[2] = 1
		for i in range(3, n + 1):
			tab[i] = (i - 1) * (tab[i - 1] % m + tab[i - 2] % m) % m
		return tab[n]


class Solution:

	def solve(n, dp):
		if n <= 1:
			return 0
		if n == 2:
			return 1
		mod = 10 ** 9 + 7
		if dp[n] != -1:
			return dp[n]
		ans = Solution.solve(n - 1, dp) + Solution.solve(n - 2, dp)
		ans = n - 1 * ans
		dp[n] = ans
		return dp[n] % mod

	def disarrange(self, n):
		mod = 10 ** 9 + 7
		der = [0 for i in range(n + 1)]
		der[1] = 0
		der[2] = 1
		for i in range(3, n + 1):
			der[i] = (i - 1) * (der[i - 1] + der[i - 2]) % mod
		return der[n]


class Solution:

	def disarrange(self, N):
		a = 0
		b = 1
		MOD = 10 ** 9 + 7
		for i in range(3, N + 1):
			cur = (i - 1) * (a + b)
			a = b
			b = cur
		return b % MOD


import sys
sys.setrecursionlimit(10 ** 9 + 7)

class Solution:

	def disarrange(self, N):

		def helper(N, memo):
			if N == 1:
				return 0
			if N == 2:
				return 1
			if not N in memo:
				memo[N] = (N - 1) * (helper(N - 1, memo) + helper(N - 2, memo))
			return memo[N]
		return helper(N, {}) % (10 ** 9 + 7)


class Solution:

	def disarrange(self, n):
		if n == 2:
			return 1
		if n == 1:
			return 0
		h = 1
		g = 0
		M = 1000000007
		for i in range(3, n + 1):
			D = (i - 1) * (h + g)
			g = h
			h = D
		return D % M


import sys

class Solution:

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


class Solution:

	def disarrange(self, N):
		if N == 1 or N == 2:
			return N - 1
		a = 0
		b = 1
		for i in range(3, N + 1):
			res = (i - 1) * (a + b)
			a = b
			b = res
		return res % (10 ** 9 + 7)


class Solution:

	def disarrange(self, N):
		if N == 1:
			return 0
		if N == 2:
			return 1
		if N == 3:
			return 2
		x = [1, 2]
		for i in range(4, N + 1):
			a = x[-1] + x[-2]
			c = (i - 1) * a
			x.append(c % 1000000007)
		return x[-1]


class Solution:

	def disarrange(self, N):
		m = 10 ** 9 + 7
		prev2 = 0
		prev1 = 1
		for i in range(3, N + 1):
			first = prev1 % m
			second = prev2 % m
			sum = first + second
			ans = (i - 1) * sum % m
			prev2 = prev1
			prev1 = ans
		return prev1
		return ans


class Solution:

	def disarrange(self, N):
		m = 10 ** 9 + 7
		dp = [-1 for i in range(N + 1)]
		dp[1] = 0
		dp[2] = 1
		for i in range(3, N + 1):
			ans1 = dp[i - 1] % m
			ans2 = dp[i - 2] % m
			sum = ans1 + ans2
			dp[i] = (i - 1) % m * sum % m
		return dp[N]
		return ans


class Solution:

	def disarrange(self, n):
		if n == 2:
			return 1
		n2 = 0
		n1 = 1
		for i in range(3, n + 1):
			temp = n1
			n1 = (i - 1) * (n1 + n2)
			n2 = temp
		return n1 % (10 ** 9 + 7)


class Solution:

	def disarrange(self, N):
		dp = [0] * (N + 1)
		MOD = 10 ** 9 + 7
		dp[1] = 0
		dp[2] = 1
		for i in range(3, N + 1):
			first = dp[i - 1] % MOD
			second = dp[i - 2] % MOD
			dp[i] = (i - 1) % MOD * (first + second) % MOD
		return dp[N]


class Solution:

	def disarrange(self, N):
		mod = 1000000000.0 + 7
		a = 0
		b = 1
		for i in range(3, N + 1):
			tmp = (i - 1) * (b + a)
			a = b % mod
			b = tmp % mod
		return int(b)


class Solution:

	def disarrange(self, n):
		p1 = 0
		p2 = 1
		res = 1
		mod = 10 ** 9 + 7
		for i in range(3, n + 1):
			res = (i - 1) * (p1 + p2) % mod
			p1 = p2 % mod
			p2 = res % mod
		return res


class Solution:

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


class Solution:

	def disarrange(self, N):
		(a, b) = (1, 0)
		mod = 10 ** 9 + 7
		for i in range(1, N + 1):
			(a, b) = ((i - 1) * (a + b) % mod, a)
		return a


class Solution:

	def disarrange(self, n):
		MOD = 1000000007
		dp = [0] * (N + 1)
		dp[1] = 0
		dp[2] = 1
		for i in range(3, N + 1):
			first = dp[i - 1] % MOD
			second = dp[i - 2] % MOD
			dp[i] = (i - 1) % MOD * (first + second) % MOD
		return dp[N]


class Solution:

	def disarrange(self, N):
		if N <= 1:
			return 0
		if N == 2:
			return 1
		x = 0
		y = 1
		for i in range(3, N + 1):
			res = (i - 1) * (x + y) % 1000000007
			x = y
			y = res
		return res


import sys
sys.setrecursionlimit(10000000)

class Solution:

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


import sys
sys.setrecursionlimit(10000000)

class Solution:

	def disarrange(self, N):

		def helper(N, dp):
			if N == 1:
				return 0
			if N == 2:
				return 1
			if dp[N] != -1:
				return dp[N]
			dp[N] = (N - 1) * (helper(N - 2, dp) + helper(N - 1, dp))
			return dp[N] % 1000000007
		dp = [-1] * (N + 1)
		return helper(N, dp)


class Solution:

	def disarrange(self, n):
		d = [0 for i in range(n + 1)]
		d[2] = 1
		for i in range(3, n + 1):
			d[i] = (i - 1) * (d[i - 1] + d[i - 2])
		return d[n] % (1000000000 + 7)


class Solution:

	def ncr(self, n, r):
		return

	def disarrange(self, N):
		mod = 10 ** 9 + 7
		a = 0
		b = 1
		if N <= 2:
			return N - 1
		temp = 0
		for i in range(3, N + 1):
			temp = (i - 1) % mod * (b % mod + a % mod) % mod
			a = b
			b = temp
		return b


class Solution:

	def disarrange(self, n):
		if n == 1:
			return 0
		mod = 10 ** 9 + 7
		(a, b) = (0, 1)
		for i in range(2, n):
			temp = i * (a + b) % mod
			(a, b) = (b % mod, temp)
		return b % mod


m = 1000000007

class Solution:

	def solve(self, n):
		if n == 1 or n == 2:
			return n - 1
		prev1 = 1
		prev2 = 0
		for i in range(3, n + 1):
			a = (i - 1) % m * (prev1 % m)
			b = (i - 1) % m * (prev2 % m)
			ans = (a + b) % m
			prev2 = prev1
			prev1 = ans
		return prev1

	def disarrange(self, n):
		return self.solve(n)


import sys
sys.setrecursionlimit(1 << 30)
mod = pow(10, 9) + 7

class Solution:

	def solve(self, N, dp):
		if N <= 1:
			return 0
		if N == 2:
			return 1
		if dp[N] != -1:
			return dp[N]
		ans = (self.solve(N - 1, dp) + self.solve(N - 2, dp)) * (N - 1) % mod
		dp[N] = ans
		return ans

	def disarrange(self, N):
		dp = [-1 for _ in range(N + 1)]
		return self.solve(N, dp)


class Solution:

	def util(self, N, T):
		if N == 0:
			return 0
		if N == 1:
			return 0
		if N == 2:
			return 1
		if T[N] != -1:
			return T[N]
		else:
			return T[N]

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


mod = [1000000007]

class Solution:

	def solve(self, n, dp):
		if n == 1:
			return 0
		if n == 2:
			return 1
		if dp[n] != -1:
			return dp[n]
		dp[n] = (n - 1) * (self.solve(n - 1, dp) + self.solve(n - 2, dp))
		return dp[n]

	def solve1(self, n):
		dp = [0 for i in range(n + 1)]
		dp[1] = 0
		dp[2] = 1
		for i in range(3, n + 1):
			a = dp[i - 1] % mod[0]
			b = dp[i - 2] % mod[0]
			sum = (a + b) % mod[0]
			ans = (i - 1) * sum % mod[0]
			dp[i] = ans
		return dp[n]

	def solve3(self, n):
		prev1 = 1
		prev2 = 0
		for i in range(3, n + 1):
			a = prev1 % mod[0]
			b = prev2 % mod[0]
			sum = (a + b) % mod[0]
			ans = (i - 1) * sum % mod[0]
			prev2 = prev1
			prev1 = ans
		return prev1

	def disarrange(self, n):
		dp = [-1 for i in range(n + 1)]
		return self.solve3(n)


class Solution:

	def Memdisarrange(self, N, dp):
		mod = 10 ** 9 + 7
		n = N
		if n == 1:
			return 0
		if n == 2:
			return n - 1
		if dp[n] != -1:
			return dp[n]
		dp[n] = (n - 1) % mod * (self.Memdisarrange(n - 1, dp) % mod + self.Memdisarrange(n - 2, dp) % mod) % mod
		return dp[n]

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


class Solution:

	def disarrange(self, N):
		countDer = [0] * (N + 1)
		countDer[1] = 0
		countDer[2] = 1
		for i in range(3, N + 1):
			countDer[i] = (i - 1) * (countDer[i - 2] + countDer[i - 1])
		return countDer[-1] % 1000000007


class Solution:

	def disarrange(self, N):
		if N == 2 or N == 3:
			return N - 1
		i1 = 1
		i2 = 2
		for i in range(3, N):
			(i1, i2) = (i2, i * (i1 + i2) % int(1000000000.0 + 7))
		return i2


MOD = [1000000007]

class Solution:

	def disarrange(self, N):
		dp = [0] * (N + 1)
		dp[1] = 0
		dp[2] = 1
		for i in range(3, N + 1):
			first = dp[i - 1] % MOD[0]
			second = dp[i - 2] % MOD[0]
			ans = (i - 1) % MOD[0] * (first + second) % MOD[0]
			dp[i] = ans
		return dp[N]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.disarrange(N))


MOD = 10 ** 9 + 7

class Solution:

	def disarrange(self, N):
		dp = [0] * (N + 1)
		dp[0] = 1
		dp[1] = 0
		dp[2] = 1
		for i in range(3, N + 1):
			dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD
		return dp[N]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.disarrange(N))


class Solution:

	def disarrange(self, n):
		arr = [0 for i in range(n + 1)]
		arr[2] = 1
		if n == 0 or n == 1:
			return 0
		else:
			for i in range(3, n + 1):
				arr[i] = (i - 1) * (arr[i - 1] + arr[i - 2]) % 1000000007
			return int(arr[n])
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.disarrange(N))


from sys import stdin, setrecursionlimit
import sys
setrecursionlimit(10 ** 6)
MOD = 1000000007

class Solution:

	def disarrange(self, n):
		return self.solve(n)

	def solve(self, n):
		prev2 = 0
		prev1 = 1
		for i in range(3, n + 1):
			summ = prev1 + prev2
			ans = (i - 1) * summ % MOD
			prev2 = prev1
			prev1 = ans
		return prev1