Given is an integer sequence of length N: A_1, A_2, \cdots, A_N.
An integer sequence X, which is also of length N, will be chosen randomly by independently choosing X_i from a uniform distribution on the integers 1, 2, \ldots, A_i for each i (1 \leq i \leq N).
Compute the expected value of the length of the longest increasing subsequence of this sequence X, modulo 1000000007.
More formally, under the constraints of the problem, we can prove that the expected value can be represented as a rational number, that is, an irreducible fraction \frac{P}{Q}, and there uniquely exists an integer R such that R \times Q \equiv P \pmod {1000000007} and 0 \leq R < 1000000007, so print this integer R.

-----Notes-----
A subsequence of a sequence X is a sequence obtained by extracting some of the elements of X and arrange them without changing the order. The longest increasing subsequence of a sequence X is the sequence of the greatest length among the strictly increasing subsequences of X.

-----Constraints-----
 - 1 \leq N \leq 6
 - 1 \leq A_i \leq 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 A_2 \cdots A_N

-----Output-----
Print the expected value modulo 1000000007.

-----Sample Input-----
3
1 2 3

-----Sample Output-----
2

X becomes one of the following, with probability 1/6 for each:
 - X = (1,1,1), for which the length of the longest increasing subsequence is 1;
 - X = (1,1,2), for which the length of the longest increasing subsequence is 2;
 - X = (1,1,3), for which the length of the longest increasing subsequence is 2;
 - X = (1,2,1), for which the length of the longest increasing subsequence is 2;
 - X = (1,2,2), for which the length of the longest increasing subsequence is 2;
 - X = (1,2,3), for which the length of the longest increasing subsequence is 3.
Thus, the expected value of the length of the longest increasing subsequence is (1 + 2 + 2 + 2 + 2 + 3) / 6 \equiv 2 \pmod {1000000007}.

Difficulty: VERY_HARD

Starter code:

Solutions:
from itertools import permutations
from bisect import bisect_left
inf = 10 ** 18
mod = 10 ** 9 + 7

def nCr(n, r, mod=10 ** 9 + 7):
	if r < 0 or r > n:
		return 0
	res = 1
	div = 1
	r = min(r, n - r)
	for i in range(r):
		res = res * (n - i) % mod
		div = div * (i + 1) % mod
	return res * pow(div, mod - 2, mod) % mod

def calc_lis(A):
	L = [A[0]]
	for a in A[1:]:
		if a > L[-1]:
			L.append(a)
		else:
			L[bisect_left(L, a)] = a
	return len(L)

def enum(N, A):
	diff = [A[0]] + [r - l for (l, r) in zip(A[:-1], A[1:])]
	dp = [[0] * (N + 1) for _ in range(N + 1)]
	dp[0][0] = 1
	for i in range(1, N + 1):
		for j in range(i, N + 1):
			for k in range(i - 1, j + 1):
				dp[i][j] += dp[i - 1][k] * nCr(diff[i - 1], j - k)
				dp[i][j] %= mod
	return dp[N][N]

def main():
	N = int(input())
	A = list(map(int, input().split()))
	pair = [(0,)]
	for _ in range(1, N):
		nxt = []
		for p in pair:
			v = p[-1]
			nxt.append(p + (v,))
			nxt.append(p + (v + 1,))
		pair = nxt
	ans = 0
	for p in pair:
		sz = p[-1] + 1
		for order in set(permutations(p)):
			arr = [inf] * sz
			for (i, a) in zip(order, A):
				arr[i] = min(arr[i], a)
			for i in reversed(range(sz - 1)):
				arr[i] = min(arr[i], arr[i + 1])
			ans += enum(sz, arr) * calc_lis(order)
			ans %= mod
	for a in A:
		ans *= pow(a, mod - 2, mod)
		ans %= mod
	print(ans)
main()


import sys
input = sys.stdin.readline
import bisect
N = int(input())
A = list(map(int, input().split()))
mod = 1000000007

def Combi(a, b):
	if b > a:
		return 0
	ANS = 1
	for i in range(min(b, a - b)):
		ANS = ANS * (a - i) * pow(min(b, a - b) - i, mod - 2, mod) % mod
	return ANS % mod

def alltuple(A):
	ANS = []
	MAX = max(A)
	if min(A) != -1:
		return [tuple(A)]
	LEN = len(A)
	for i in range(LEN):
		if A[i] == -1:
			if MAX != -1:
				A[i] = MAX
				ANS += alltuple(A)
			A[i] = MAX + 1
			ANS += alltuple(A)
			A[i] = -1
	return ANS
ALLX = set(alltuple([-1] * N))

def LIS(A):
	LEN = len(A)
	DP = [float('inf')] * LEN
	for a in A:
		pos = bisect.bisect_left(DP, a)
		DP[pos] = a
	ANS = 0
	for i in range(LEN):
		if DP[i] != float('inf'):
			ANS = i
	return ANS + 1
ANS = 0
KOSUU = 0
for tu in ALLX:
	LIS_tu = LIS(tu)
	B = []
	for i in range(max(tu) + 1):
		MIN = 1 << 30
		for j in range(N):
			if tu[j] == i:
				MIN = min(MIN, A[j])
		B.append(MIN)
	for i in range(len(B) - 2, -1, -1):
		B[i] = min(B[i], B[i + 1])
	SB = [0] + sorted(set(B))
	compression_dict = {a: ind for (ind, a) in enumerate(SB)}
	BC = [compression_dict[m] for m in B]
	LEN = len(B)
	DPLEN = len(SB)
	DP = [[0] * DPLEN for i in range(LEN + 1)]
	DP[0][0] = 1
	for i in range(LEN):
		for j in range(DPLEN):
			if DP[i][j] == 0:
				continue
			for k in range(j + 1, DPLEN):
				if k > BC[i]:
					break
				for l in range(i + 1, LEN + 1):
					DP[l][k] += DP[i][j] * Combi(SB[k] - SB[k - 1], l - i)
					DP[l][k] %= mod
	KOSUU += sum(DP[-1])
	ANS += sum(DP[-1]) * LIS_tu
print(ANS * pow(KOSUU, mod - 2, mod) % mod)


SIZE = 10
MOD = 10 ** 9 + 7
inv = [0] * SIZE
inv[1] = 1
for i in range(2, SIZE):
	inv[i] = MOD - MOD // i * inv[MOD % i] % MOD

def solve(a):
	n = len(a)
	for i in range(n - 2, -1, -1):
		if a[i] > a[i + 1]:
			a[i] = a[i + 1]
	if a[0] < 0:
		return 0
	A = a[-1] + 1
	res = [[0, 0, 1]]
	for ai in a:
		val = 0
		for r in res:
			(bi, ki, ti) = r
			val += ti
			r[1] += 1
			r[2] = r[2] * (A - bi + ki + 1) % MOD * inv[ki + 1] % MOD
		res.append([ai + 1, 1, -val % MOD * (A - ai) % MOD])
	return sum((r[2] for r in res)) % MOD
from bisect import bisect_left

def LIS(a):
	n = len(a)
	dp = [n + 1] * n
	for i in a:
		dp[bisect_left(dp, i)] = i
	return bisect_left(dp, n + 1)
from itertools import permutations
n = int(input())
(*a,) = map(int, input().split())
ans = 0
for x in permutations(range(n)):
	b = [a[i] - 1 for i in x]
	offset = 0
	for i in range(n):
		b[i] -= offset
		if i + 1 < n and x[i] < x[i + 1]:
			offset += 1
	ans += LIS(x) * solve(b)
	ans %= MOD
c = 1
for i in a:
	c *= i
	c %= MOD
ans *= pow(c, MOD - 2, MOD)
print(ans % MOD)


MOD = 10 ** 9 + 7
from itertools import product
from bisect import bisect
from collections import Counter

def lis(N, A):
	INF = 1000
	dp = [INF] * (N + 1)
	dp[0] = -1
	for a in A:
		idx = bisect(dp, a - 1)
		dp[idx] = min(a, dp[idx])
	return max((i for i in range(N + 1) if dp[i] < INF))

def multisigma(n, x):
	res = 1
	for i in range(n):
		res *= x - i
		res *= pow(i + 1, MOD - 2, MOD)
		res %= MOD
	return res

def dfs(R, num, tmp):
	nonlocal ans
	n = len(R)
	if tmp == n:
		ans += num * lis(n, R)
		ans %= MOD
		return
	l = len(space[tmp])
	if l == 0:
		dfs(R, num, tmp + 1)
		return
	for P in product(range(l), repeat=l):
		P = list(P)
		m = len(set(P))
		if m != max(P) + 1:
			continue
		if m > zone[tmp]:
			continue
		for (x, y) in zip(P, space[tmp]):
			R[y] = x + tmp * 10
		nxt = num * multisigma(m, zone[tmp]) % MOD
		dfs(R, nxt, tmp + 1)
	return
n = int(input())
a = list(map(int, input().split()))
b = sorted(list(set(a)))
zone = [b[0]]
for i in range(1, len(b)):
	zone.append(b[i] - b[i - 1])
d = dict()
tmp = 0
h = [-1 for _ in range(n)]
for (i, z) in enumerate(zone):
	tmp += z
	d[tmp] = i
for (i, x) in enumerate(a):
	h[i] = d[x]
k = len(zone)
ans = 0
for P in product(range(k), repeat=n):
	ok = True
	P = list(P)
	for (i, p) in enumerate(P):
		if p > h[i]:
			ok = False
			break
	if not ok:
		continue
	space = [[] for _ in range(n)]
	for (i, p) in enumerate(P):
		space[p].append(i)
	c = Counter(P)
	R = [-1 for _ in range(n)]
	dfs(R, 1, 0)
for x in a:
	ans *= pow(x, MOD - 2, MOD)
	ans %= MOD
print(ans)


import itertools
P = 10 ** 9 + 7
fainv = [1, 1, 500000004, 166666668, 41666667, 808333339, 301388891]

def C(a, b):
	s = 1
	for i in range(b):
		s = s * (a - i) % P
	return s * fainv[b] % P

def calc(LL):
	L = LL[:]
	K = len(L)
	for i in range(K - 1)[::-1]:
		L[i] = min(L[i], L[i + 1])
	for i in range(1, K)[::-1]:
		L[i] -= L[i - 1]
	X = [0] * K
	f = 1
	re = 0
	cnt = 0
	while f:
		for (x1, x2) in zip(X, X[1:]):
			if x1 > x2:
				break
		else:
			Y = [0] * K
			for x in X:
				Y[x] += 1
			t = 1
			for (j, y) in enumerate(Y):
				t = t * C(L[j], y) % P
			re += t
		cnt += 1
		X[0] += 1
		i = 0
		while X[i] == i + 1:
			X[i] = 0
			i += 1
			if i >= K:
				f = 0
				break
			X[i] += 1
	return re
N = int(input())
Q = list(itertools.permutations(range(N)))
A = [int(a) for a in input().split()]

def LIS(l):
	n = len(l)
	X = [-1] + [n] * n
	for a in l:
		for i in range(n, -1, -1):
			if X[i] < a:
				X[i + 1] = a
				break
	for i in range(n, -1, -1):
		if X[i] < n:
			return i
ans = 0
chk = 0
for q in Q:
	L = []
	s = 0
	for i in range(N):
		if i and q[i - 1] >= q[i]:
			s += 1
		L.append(A[q[i]] + s)
	calcL = calc(L)
	LISq = LIS(q)
	chk += calcL
	ans += calcL * LISq
	if ans >= P:
		ans -= P
s = 1
for a in A:
	s = s * a % P
ans = ans * pow(s, P - 2, P) % P
print(ans)


from bisect import bisect_left

def LIS(N, A):
	A = list(A)
	lis = []
	for i in range(N):
		ind = bisect_left(lis, A[i])
		if ind == len(lis):
			lis.append(A[i])
		else:
			lis[ind] = A[i]
	return len(lis)

def comb(n, r):
	if not 0 <= r <= n:
		return 0
	ans = 1
	for i in range(r):
		ans *= n - i
	for i in range(r):
		ans //= i + 1
	return ans

def compress(arr):
	XS = list(set(arr))
	XS.sort()
	dic = {e: i for (i, e) in enumerate(XS)}
	for i in range(len(arr)):
		arr[i] = dic[arr[i]]
	return arr
from itertools import groupby, accumulate, product, permutations, combinations
N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
from collections import defaultdict

def gutyoku(N, A):
	cnt = 0
	for a in range(1, A[0] + 1):
		if N == 1:
			B = [a]
			cnt += LIS(N, B)
			continue
		for b in range(1, A[1] + 1):
			if N == 2:
				B = [a, b]
				cnt += LIS(N, B)
				continue
			for c in range(1, A[2] + 1):
				if N == 3:
					B = [a, b, c]
					cnt += LIS(N, B)
					continue
				for d in range(1, A[3] + 1):
					if N == 4:
						B = [a, b, c, d]
						cnt += LIS(N, B)
						continue
					for e in range(1, A[4] + 1):
						if N == 5:
							B = [a, b, c, d, e]
							cnt += LIS(N, B)
							continue
						for f in range(1, A[5] + 1):
							B = [a, b, c, d, e, f]
							cnt += LIS(N, B)
	return cnt

def solve(N, A):
	ans = 0
	dic = defaultdict(lambda : 0)
	for pro in product([0, 1], repeat=N - 1):
		lis = [1] * N
		pro = list(pro)
		for i in range(N - 1):
			lis[i + 1] = lis[i] + pro[i]
		for perm in permutations(lis, N):
			if dic[perm] == 1:
				continue
			dic[perm] = 1
			num = max(perm)
			lis2 = [0] + [10 ** 10] * num
			for (i, p) in enumerate(perm):
				lis2[p] = min(lis2[p], A[i])
			for i in range(num - 1, 0, -1):
				lis2[i] = min(lis2[i], lis2[i + 1])
			comp = lambda arr: {i: e for (i, e) in enumerate(sorted(set(arr)))}
			compdic = comp(lis2)
			complis2 = compress(lis2[:])
			M = max(complis2)
			dp = [[0] * (M + 1) for _ in range(num + 1)]
			dp[0][0] = 1
			for i in range(1, num + 1):
				for j in range(1, complis2[i] + 1):
					for k in range(j):
						dp[i][j] += dp[i - 1][k] * (compdic[j] - compdic[j - 1])
					for k in range(i - 1, 0, -1):
						if complis2[k] < j:
							break
						dp[i][j] += sum(dp[k - 1][:j]) * comb(compdic[j] - compdic[j - 1], i - k + 1)
			ans += sum(dp[-1]) * LIS(N, perm)
	return ans
ans2 = solve(N, A)
for i in range(N):
	ans2 *= pow(A[i], mod - 2, mod)
	ans2 %= mod
print(ans2)