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: competition

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):# 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):
    #print(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 # DP[i]で、長さiのLISの最終要素の最小値.

    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"): # float("inf")でない最小のものがLISの長さ
            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 #998244353 #ここを変更する
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
	#print(R, num, tmp)
	n = len(R)
	if tmp == n:
		#print(R, lis(n, R))
		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]
#print(h)
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]
    # print("L =", L)
    X = [0] * K
    f = 1
    re = 0
    cnt = 0 # Check用
    while f:

        # ここに処理を書く
        # if cnt < 20: print("cnt, X =", cnt, X)
        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
            # print("X, Y, t =", X, Y, t)
            re += t
        cnt += 1 # Check用

        X[0] += 1
        i = 0
        while X[i] == i + 1: # ここにi番目の終了条件を書く
            X[i] = 0
            i += 1
            if i >= K:
                f = 0
                break
            X[i] += 1

    # print(cnt)
    return re

# print(calc([4, 4, 4]))

N = int(input())
Q = list(itertools.permutations(range(N)))
A = [int(a) for a in input().split()]
# print("Q =", Q)
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:
    # print(q, LIS(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
    # print("q =", q, L, calcL, LISq)
    ans += calcL * LISq
    if ans >= P: ans -= P
# print("chk = ", chk)
s = 1
for a in A:
    s = s * a % P

ans = ans * pow(s, P-2, P) % P
print(ans)

import sys
input = sys.stdin.readline
import bisect

N=int(input())
A=list(map(int,input().split()))

mod=1000000007

def Combi(a,b):# 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):
    #print(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 # DP[i]で、長さiのLISの最終要素の最小値.

    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"): # float("inf")でない最小のものがLISの長さ
            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)

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)
  # debug = defaultdict(lambda: [0,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])
      # cnt = 0
      # j = 0
      # cum = 1
      # for i in range(1,num+1):
      #   if lis2[i]-lis2[j]==0:
      #     continue
      #   if j-1>=0:
      #     cum *= comb(lis2[i-1]-lis2[j-1],i-j)
      #   cnt += cum*comb(lis2[i]-lis2[j],num+1-i)
      #   j = i
      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)
      # debug[tuple(lis2)][0] = sum(dp[-1])
      # debug[tuple(lis2)][1] += LIS(N,perm)
      # print(list(perm),lis2,sum(dp[-1]),LIS(N,perm))
  # for k,v in debug.items():
    # print(k,v)
  return ans
# ans1 = gutyoku(N,A)
ans2 = solve(N,A)
for i in range(N):
  ans2 *= pow(A[i],mod-2,mod)
  ans2 %= mod
print(ans2)
# if ans1!=ans2:
  # print(ans1,ans2)