You are given an array A of integers of length N. You need to calculate factorial of each number. The answer can be very large, so print it modulo 10^{9 }+ 7.
 
Example 1:
Input:
N = 5
A[] = {0, 1, 2, 3, 4}
Output:
1 1 2 6 24
Explanation:
Factorial of 0 is 1, 
factorial of 1 is 1, factorial of 2 is 2, 
factorial of 3 is 6 and so on.
Example 2:
Input:
N = 3
A[] = {5, 6, 3}
Output:
120 720 6
Explanation:
Factorial of 5 is 120, 
factorial of 6 is 720, 
factorial of 3 is 6.
Your Task:
Complete the function factorial() which takes list a and single integer n, as input parameters and returns a list of factorials of the numbers in the list a.
Expected Time Complexity: O(max(A) + N)
Expected Auxiliary Space: O(max(A))
Constraints:
1 <= N <= 10^{5}
0 <= A[i] <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Mathematics

Starter code: #User function Template for python3

class Solution:



	def factorial(self,a, n):

    	# code here



Solutions:
class Solution:

	def factorial(self, a, n):
		m = 10 ** 9 + 7
		ans = []
		maxi = max(a)
		dp = [1] * (maxi + 1)
		for i in range(2, maxi + 1):
			dp[i] = i * dp[i - 1] % m
		for i in a:
			ans.append(dp[i])
		return ans


class Solution:

	def factorial(self, a, n):
		result = []
		fact_dict = {}
		maximum = a[0]
		m = 10 ** 9 + 7
		for i in range(1, n):
			maximum = max(maximum, a[i])
		fact_dict[0] = 1
		fact_dict[1] = 1
		for j in range(2, maximum + 1):
			fact_dict[j] = j * fact_dict[j - 1] % m
		for i in range(n):
			result.append(fact_dict[a[i]])
		return result


import math as m

class Solution:

	def factorial(self, a, n):
		mod = 1000000007
		fact = [1] * (max(a) + 1)
		for i in range(2, max(a) + 1):
			fact[i] = fact[i - 1] * i % mod
		result = []
		for i in range(n):
			result.append(fact[a[i]])
		return result


class Solution:

	def factorial(self, a, n):
		ans = [1, 1]
		m = 1000000007
		current = 1
		for i in range(2, max(a) + 1):
			current *= i
			current %= m
			ans.append(current)
		x = []
		for i in a:
			x.append(ans[i])
		return x


class Solution:

	def factorial(self, a, n):
		maxi = max(a)
		d = dict()
		prod = 1
		for i in range(0, maxi + 1):
			prod = prod * max(i, 1) % (10 ** 9 + 7)
			d[i] = prod
		ans = []
		for num in a:
			ans.append(d[num])
		return ans


class Solution:

	def factorial(self, a, n):
		m = 10 ** 9 + 7
		arr = [0] * (max(a) + 1)
		arr[0] = 1
		for i in range(1, len(arr)):
			arr[i] = i * arr[i - 1] % m
		for i in range(n):
			a[i] = arr[a[i]]
		return a


class Solution:

	def factorial(self, a, n):
		m = 10 ** 9 + 7
		ans = []
		maxi = max(a)
		fact = [1, 1]
		f = 1
		for i in range(2, maxi + 1):
			f *= i
			f %= m
			fact.append(f)
		for i in a:
			ans.append(fact[i])
		return ans
0


class Solution:

	def factorial(self, a, n):
		mod = int(1000000000.0 + 7)
		m = max(a)
		if m == 0:
			return 1
		dp = [0] * (m + 1)
		dp[0] = 1
		for i in range(1, m + 1):
			dp[i] = dp[i - 1] * i
			dp[i] = dp[i] % mod
		for i in range(n):
			a[i] = dp[a[i]]
		return a


class Solution:

	def factorial(self, a, n):
		facts = [1]
		maxA = 0
		for i in a:
			maxA = max(maxA, i)
		f = 1
		mod = 10 ** 9 + 7
		for i in range(1, maxA + 1):
			f *= i
			f %= mod
			facts.append(f)
		res = []
		for i in a:
			res.append(facts[i])
		return res


class Solution:

	def factorial(self, a, n):
		d = {}
		MOD = 1000000007
		for i in range(n):
			d[a[i]] = 1
		m = max(a)
		ans = 1
		for i in range(1, m + 1):
			ans = ans * i % MOD
			if i in d.keys():
				d[i] = ans
		for i in range(n):
			a[i] = d[a[i]]
		return a


class Solution:

	def factorial(self, a, n):
		m = max(a)
		f = [1]
		for i in range(1, m + 1):
			f.append(f[-1] * i % (10 ** 9 + 7))
		res = []
		for i in a:
			res.append(f[i])
		return res


class Solution:

	def factorial(self, a, n):
		m = 1000000000.0 + 7
		mx = max(a)
		dp = [0] * (mx + 1)
		dp[0:3] = [1, 1, 2]
		for i in range(3, mx + 1):
			dp[i] = int(i * dp[i - 1] % m)
		res = [0] * n
		for i in range(n):
			res[i] = dp[a[i]]
		return res


class Solution:

	def factorial(self, a, n):
		maximum = max(a)
		res = []
		dp = [1] * (maximum + 1)
		for i in range(1, maximum + 1):
			dp[i] = i * dp[i - 1] % 1000000007
		for val in a:
			res.append(dp[val])
		return res


class Solution:

	def factorial(self, a, n):
		a1 = {0: 1}
		a2 = max(a)
		p = 1
		for i in range(1, a2 + 1):
			p *= i
			p %= 1000000007
			a1[i] = p
		d = []
		for i in a:
			d.append(a1[i])
		return d


class Solution:

	def factorial(self, a, n):
		arr = [1]
		output = []
		for item in a:
			while item > len(arr) - 1:
				arr.append(arr[-1] * len(arr) % (10 ** 9 + 7))
			output.append(arr[item])
		return output


class Solution:

	def factorial(self, a, n):
		d2 = {}
		mx = -1
		for x in a:
			d2[x] = 1
			mx = max(mx, x)
		d = {0: 1}
		s = 1
		for x in range(1, mx + 1):
			s = s * x % 1000000007
			if d2.get(x):
				d[x] = s
		l = []
		for x in a:
			l.append(d.get(x))
		return l


class Solution:

	def __init__(self):
		self.dp = dict()

	def factorial(self, a, n):
		self.dp.clear()
		self.dp = {0: 1}
		m = max(a)
		a_ = {x: 1 for x in a}
		i = 1
		for x in range(1, m + 1):
			i = i * x % (10 ** 9 + 7)
			if a_.get(x) == 1:
				self.dp[x] = i
		return [self.dp[x] for x in a]


class Solution:

	def factorial(self, a, n):
		res = list()
		maxi = max(a)
		dp = [1] * (maxi + 1)
		mod = 10 ** 9 + 7
		for i in range(1, maxi + 1):
			dp[i] = i * dp[i - 1] % mod
		for val in a:
			res.append(dp[val])
		return res


class Solution:

	def factorial(self, a, n):
		hash = {0: 1}
		result = []
		max_val = max(a)
		fact = 1
		for i in range(1, max_val + 1):
			fact = fact * i % (pow(10, 9) + 7)
			hash[i] = fact
		for i in a:
			result.append(hash[i])
		return result


class Solution:

	def factorial(self, a, n):
		x = max(a)
		l = [1, 1]
		for i in range(2, x + 1):
			c = i * l[-1] % 1000000007
			l.append(c)
		for i in range(n):
			a[i] = l[a[i]]
		return a


class Solution:

	def factorial(self, a, n):
		MAX = 10 ** 5
		fac = [0] * (MAX + 1)
		mod = 10 ** 9 + 7
		fac[0] = 1
		for i in range(1, MAX + 1):
			fac[i] = fac[i - 1] % mod * i % mod
		ans = [0] * n
		for i in range(0, n):
			ans[i] = fac[a[i]]
		return ans


class Solution:

	def factorial(self, a, n):
		num = max(a)
		m = 1000000007
		fact = [0 for i in range(n)]
		dict_fact = dict()
		dict_fact[0] = 1
		for i in range(1, num + 1):
			dict_fact[i] = i * dict_fact[i - 1] % m
		for i in range(n):
			fact[i] = dict_fact[a[i]]
		return fact


class Solution:

	def factorial(self, a, n):
		m = max(a)
		mo = 1000000007
		dic = {}
		dic[0] = 1
		for i in range(1, m + 1):
			dic[i] = dic[i - 1] * i % mo
		for i in range(n):
			a[i] = dic[a[i]]
		return a


class Solution:

	def factorial(self, a, n):
		f = [1, 1]
		ans = 1
		MOD = 10 ** 9 + 7
		for i in range(2, 10 ** 5 + 5):
			ans = ans % MOD * i % MOD % MOD
			f.append(ans)
		ans = []
		for i in range(n):
			a[i] = f[a[i]]
		return a


class Solution:

	def factorial(self, a, n):
		maximum = -1
		arr = []
		for i in range(n):
			if a[i] > maximum:
				maximum = a[i]
		arr.append(1)
		for i in range(1, maximum + 1, 1):
			arr.append(arr[i - 1] * i % (10 ** 9 + 7))
		for i in range(n):
			a[i] = arr[a[i]]
		return a


class Solution:

	def factorial(self, a, n):
		maximum = max(a) + 1
		factdp = [1, 1]
		for i in range(2, maximum):
			factdp.append(i * factdp[-1] % 1000000007)
		for i in range(n):
			a[i] = factdp[a[i]]
		return a


class Solution:
	m = 10 ** 9 + 7

	def factorial(self, a, n):
		fact = [1, 1]
		l = []
		for i in range(2, max(a) + 1):
			k = i * fact[i - 1] % self.m
			fact.append(k)
		for j in a:
			l.append(fact[j] % self.m)
		return l


fac = [1]
mod = 1000000007
for i in range(1, 100001):
	fac.append(fac[-1] % mod * i % mod)

class Solution:

	def factorial(self, a, n):
		global fac
		result = []
		for i in a:
			result.append(fac[i])
		return result


class Solution:

	def factorial(self, a, n):
		N = max(a)
		d = {}
		(d[0], ans) = (1, 1)
		for i in range(1, N + 1):
			ans = ans * i
			ans = ans % 1000000007
			d[i] = ans
		for i in range(n):
			a[i] = d[a[i]]
		return a


class Solution:

	def factorial(self, a, n):
		maxi = max(a)
		ans = []
		dp = [1] * (maxi + 1)
		for i in range(1, maxi + 1):
			dp[i] = i * dp[i - 1] % 1000000007
		for val in a:
			ans.append(dp[val])
		return ans


import math as m

class Solution:

	def factorial(self, a, n):
		mx = max(a)
		fact = [1] * (mx + 1)
		ans = [] * n
		mod = 1000000000.0 + 7
		for i in range(1, mx + 1):
			fact[i] = fact[i - 1] * i % mod
		for i in a:
			ans.append(int(fact[i]))
		return ans


class Solution:

	def factorial(self, a, n):
		max_range = 10 ** 5
		fact = [0] * (max_range + 1)
		fact[0] = 1
		mod = 10 ** 9 + 7
		for i in range(1, max_range + 1):
			fact[i] = fact[i - 1] % mod * i % mod
		ans = [0] * n
		for i in range(n):
			ans[i] = fact[a[i]]
		return ans


import math

class Solution:

	def factorial(self, a, n):
		maximum = max(a)
		dp = [1] * (maximum + 1)
		for i in range(1, maximum + 1):
			dp[i] = i * dp[i - 1] % 1000000007
		return [dp[val] for val in a]


class Solution:

	def factorial(self, a, n):
		x = max(a)
		dp = [0] * (x + 1)
		dp[0] = 1
		dp[1] = 1
		for i in range(2, x + 1):
			dp[i] = i * dp[i - 1] % (10 ** 9 + 7)
		fans = []
		for i in a:
			fans.append(dp[i])
		return fans


class Solution:

	def __init__(self):
		self.facts = {}
		self.facts[0] = 1
		self.facts[1] = 1
		self.mod = 1000000007

	def factorial(self, a, n):
		max_a = max(a)
		for i in range(2, max_a + 1):
			self.facts[i] = self.facts[i - 1] * i % self.mod
		return [self.facts[x] for x in a]


class Solution:

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


import math

class Solution:

	def factorial(self, a, n):
		l = []
		m = max(a)
		arr = [1] * (m + 1)
		for i in range(1, m + 1):
			arr[i] = i * arr[i - 1] % 1000000007
		for j in a:
			l.append(arr[j])
		return l


class Solution:

	def fact(self, num):
		f = 1
		for i in range(1, num + 1):
			f *= i
		return f

	def factorial(self, a, n):
		fact = {}
		fact[0] = 1
		MAX = pow(10, 5)
		mod = pow(10, 9) + 7
		for i in range(1, MAX + 1):
			fact[i] = i * fact[i - 1] % mod
		for (i, ele) in enumerate(a):
			a[i] = fact[ele]
		return a


class Solution:

	def factorial(self, a, n):
		ans = [0] * n
		max = 0
		for i in range(n):
			if a[i] > max:
				max = a[i]
		size = max + 1
		fact = [None] * size
		fact[0] = 1
		for i in range(1, size):
			fact[i] = i * fact[i - 1] % 1000000007
		for i in range(n):
			ans[i] = fact[a[i]]
		return ans


class Solution:

	def factorial(self, a, n):
		maxEle = max(a)
		res = []
		fact = [1] * (maxEle + 1)
		for i in range(2, maxEle + 1):
			fact[i] = fact[i - 1] * i % 1000000007
		for i in a:
			res.append(fact[i])
		return res


class Solution:

	def factorial(self, a, n):
		maxm = max(a)
		t = [1] * (maxm + 1)
		res = []
		for i in range(1, maxm + 1):
			t[i] = i * t[i - 1] % (10 ** 9 + 7)
		for val in a:
			res.append(t[val])
		return res


class Solution:

	def factorial(self, a, n):
		f = [0] * 100002
		f[0] = 1
		f[1] = 1
		arr = []
		j = 2
		for i in a:
			if f[i] != 0:
				arr.append(f[i])
			else:
				while j <= i:
					f[j] = f[j - 1] * j % (10 ** 9 + 7)
					j = j + 1
				arr.append(f[i])
		return arr


class Solution:

	def factorial(self, a, n):
		m = {0: 1}
		p = 1
		g = max(a)
		for i in range(1, g + 1):
			p = p * i
			p = p % 1000000007
			m[i] = p
		b = []
		for i in a:
			b.append(m[i])
		return b


class Solution:

	def factorial(self, a, n):
		m = -999
		for i in range(n):
			m = max(m, a[i])
		d = dict()
		d[0] = 1
		d[1] = 1
		for i in range(2, m + 1):
			d[i] = i * d[i - 1] % 1000000007
		ans = []
		for i in range(n):
			ans.append(d[a[i]])
		return ans
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		a = list(map(int, input().strip().split()))
		ob = Solution()
		res = ob.factorial(a, n)
		for i in res:
			print(i, end=' ')
		print()
		tc = tc - 1


class Solution:

	def factorial(self, arr, n):
		ans = []
		f = [1] * (max(arr) + 1)
		for i in range(1, max(arr) + 1):
			f[i] = i * f[i - 1] % 1000000007
		for i in range(len(arr)):
			ans.append(f[arr[i]])
		return ans
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		a = list(map(int, input().strip().split()))
		ob = Solution()
		res = ob.factorial(a, n)
		for i in res:
			print(i, end=' ')
		print()
		tc = tc - 1


class Solution:

	def factorial(self, a, n):
		m = max(a)
		l = 100000007
		dp = [1] * (m + 1)
		for i in range(1, m + 1):
			dp[i] = i * dp[i - 1] % 1000000007
		ans = []
		for i in a:
			ans.append(dp[i])
		return ans
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		a = list(map(int, input().strip().split()))
		ob = Solution()
		res = ob.factorial(a, n)
		for i in res:
			print(i, end=' ')
		print()
		tc = tc - 1


import math

class Solution:

	def factorial(self, a, n):
		maximum = max(a)
		res = []
		dp = [1] * (maximum + 1)
		for i in range(1, maximum + 1):
			dp[i] = i * dp[i - 1] % 1000000007
		for val in a:
			res.append(dp[val])
		return res
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		a = list(map(int, input().strip().split()))
		ob = Solution()
		res = ob.factorial(a, n)
		for i in res:
			print(i, end=' ')
		print()
		tc = tc - 1


class Solution:

	def factorial(self, a, n):
		m = max(a)
		dp = [-1] * (m + 1)
		dp[0] = 1
		dp[1] = 1
		for i in range(2, m + 1):
			dp[i] = i * dp[i - 1] % (10 ** 9 + 7)
		v = []
		for i in range(n):
			v.append(dp[a[i]])
		return v
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		a = list(map(int, input().strip().split()))
		ob = Solution()
		res = ob.factorial(a, n)
		for i in res:
			print(i, end=' ')
		print()
		tc = tc - 1


import math as sa
m1 = 1000000000.0 + 7

class Solution:

	def factorial(self, a, n):
		m = max(a)
		ans = []
		res = [1] * (max(a) + 1)
		res[1] = 1
		for i in range(2, max(a) + 1):
			res[i] = i % m1 * (res[i - 1] % m1) % m1
		for i in a:
			ans.append(sa.ceil(res[i]))
		return ans
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		a = list(map(int, input().strip().split()))
		ob = Solution()
		res = ob.factorial(a, n)
		for i in res:
			print(i, end=' ')
		print()
		tc = tc - 1


class Solution:

	def factorial(self, a, n):
		mod = 10 ** 9 + 7
		k = max(a)
		ans = []
		fact = [i % (10 ** 9 + 7) for i in range(k + 1)]
		fact[0] = 1
		for i in range(1, k + 1):
			fact[i] = fact[i - 1] * fact[i] % mod
		for i in a:
			ans.append(fact[i])
		return ans
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		a = list(map(int, input().strip().split()))
		ob = Solution()
		res = ob.factorial(a, n)
		for i in res:
			print(i, end=' ')
		print()
		tc = tc - 1


class Solution:

	def factorial(self, a, n):
		m = 1000000000.0 + 7
		lista = [_ for _ in range(n)]
		fact = [_ for _ in range(100005)]
		fact[0] = fact[1] = 1
		for i in range(2, 100005):
			fact[i] = int(fact[i] * fact[i - 1] % m)
		for i in range(n):
			lista[i] = fact[a[i]]
		return lista
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		a = list(map(int, input().strip().split()))
		ob = Solution()
		res = ob.factorial(a, n)
		for i in res:
			print(i, end=' ')
		print()
		tc = tc - 1