1292_F. Nora's Toy Boxes
[SIHanatsuka - EMber](https://soundcloud.com/hanatsuka/sihanatsuka-ember)

[SIHanatsuka - ATONEMENT](https://soundcloud.com/hanatsuka/sihanatsuka-atonement)

Back in time, the seven-year-old Nora used to play lots of games with her creation ROBO_Head-02, both to have fun and enhance his abilities.

One day, Nora's adoptive father, Phoenix Wyle, brought Nora n boxes of toys. Before unpacking, Nora decided to make a fun game for ROBO.

She labelled all n boxes with n distinct integers a_1, a_2, …, a_n and asked ROBO to do the following action several (possibly zero) times:

  * Pick three distinct indices i, j and k, such that a_i ∣ a_j and a_i ∣ a_k. In other words, a_i divides both a_j and a_k, that is a_j mod a_i = 0, a_k mod a_i = 0. 
  * After choosing, Nora will give the k-th box to ROBO, and he will place it on top of the box pile at his side. Initially, the pile is empty. 
  * After doing so, the box k becomes unavailable for any further actions. 



Being amused after nine different tries of the game, Nora asked ROBO to calculate the number of possible different piles having the largest amount of boxes in them. Two piles are considered different if there exists a position where those two piles have different boxes.

Since ROBO was still in his infant stages, and Nora was still too young to concentrate for a long time, both fell asleep before finding the final answer. Can you help them?

As the number of such piles can be very large, you should print the answer modulo 10^9 + 7.

Input

The first line contains an integer n (3 ≤ n ≤ 60), denoting the number of boxes.

The second line contains n distinct integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 60), where a_i is the label of the i-th box.

Output

Print the number of distinct piles having the maximum number of boxes that ROBO_Head can have, modulo 10^9 + 7.

Examples

Input


3
2 6 8


Output


2


Input


5
2 3 4 9 12


Output


4


Input


4
5 7 2 9


Output


1

Note

Let's illustrate the box pile as a sequence b, with the pile's bottommost box being at the leftmost position.

In the first example, there are 2 distinct piles possible: 

  * b = [6] ([2, 6, 8] \xrightarrow{(1, 3, 2)} [2, 8]) 
  * b = [8] ([2, 6, 8] \xrightarrow{(1, 2, 3)} [2, 6]) 



In the second example, there are 4 distinct piles possible: 

  * b = [9, 12] ([2, 3, 4, 9, 12] \xrightarrow{(2, 5, 4)} [2, 3, 4, 12] \xrightarrow{(1, 3, 4)} [2, 3, 4]) 
  * b = [4, 12] ([2, 3, 4, 9, 12] \xrightarrow{(1, 5, 3)} [2, 3, 9, 12] \xrightarrow{(2, 3, 4)} [2, 3, 9]) 
  * b = [4, 9] ([2, 3, 4, 9, 12] \xrightarrow{(1, 5, 3)} [2, 3, 9, 12] \xrightarrow{(2, 4, 3)} [2, 3, 12]) 
  * b = [9, 4] ([2, 3, 4, 9, 12] \xrightarrow{(2, 5, 4)} [2, 3, 4, 12] \xrightarrow{(1, 4, 3)} [2, 3, 12]) 



In the third sequence, ROBO can do nothing at all. Therefore, there is only 1 valid pile, and that pile is empty.
```python
MOD = 1000000007


def isSubset(a, b):
	return (a & b) == a


def isIntersect(a, b):
	return (a & b) != 0


# Solve for each weakly connected component (WCC)
def cntOrder(s, t):
	p = len(s)
	m = len(t)

	inMask = [0 for i in range(m)]

	for x in range(p):
		for i in range(m):
			if t[i] % s[x] == 0:
				inMask[i] |= 1 << x

	cnt = [0 for mask in range(1<<p)]
	for mask in range(1<<p):
		for i in range(m):
			if isSubset(inMask[i], mask):
				cnt[mask] += 1

	dp = [[0 for mask in range(1<<p)] for k in range(m+1)]
	for i in range(m):
		dp[1][inMask[i]] += 1
	for k in range(m):
		for mask in range(1<<p):
			for i in range(m):
				if not isSubset(inMask[i], mask) and isIntersect(inMask[i], mask):
					dp[k+1][mask | inMask[i]] = (dp[k+1][mask | inMask[i]] + dp[k][mask]) % MOD
			dp[k+1][mask] = (dp[k+1][mask] + dp[k][mask] * (cnt[mask] - k)) % MOD

	return dp[m][(1<<p)-1]


def dfs(u):
	global a, graph, degIn, visited, s, t

	visited[u] = True
	if degIn[u] == 0:
		s.append(a[u])
	else:
		t.append(a[u])

	for v in graph[u]:
		if not visited[v]:
			dfs(v)


def main():
	global a, graph, degIn, visited, s, t

	# Reading input
	n = int(input())
	a = list(map(int, input().split()))

	# Pre-calculate C(n, k)
	c = [[0 for j in range(n)] for i in range(n)]
	for i in range(n):
		c[i][0] = 1
		for j in range(1, i+1):
			c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD	

	# Building divisibility graph
	degIn = [0 for u in range(n)]
	graph = [[] for u in range(n)]
	for u in range(n):
		for v in range(n):
			if u != v and a[v] % a[u] == 0:
				graph[u].append(v)
				graph[v].append(u)
				degIn[v] += 1

	# Solve for each WCC of divisibility graph and combine result
	ans = 1
	curLen = 0
	visited = [False for u in range(n)]
	for u in range(n):
		if not visited[u]:
			s = []
			t = []
			dfs(u)

			if len(t) > 0:
				sz = len(t) - 1
				cnt = cntOrder(s, t)

				# Number of orders for current WCC
				ans = (ans * cnt) % MOD
				# Number of ways to insert <sz> number to array of <curLen> elements
				ans = (ans * c[curLen + sz][sz]) % MOD
				curLen += sz		

	print(ans)

if __name__ == "__main__":
	main()
```