{"raw_statement":[{"iden":"problem statement","content":"Given is an integer sequence of length $N$: $A_1, A_2, \\cdots, A_N$.\nAn 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)$.\nCompute the expected value of the length of the longest increasing subsequence of this sequence $X$, modulo $1000000007$.\nMore 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$."},{"iden":"notes","content":"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$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 6$\n*   $1 \\leq A_i \\leq 10^9$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\cdots$ $A_N$"},{"iden":"sample input 1","content":"3\n1 2 3"},{"iden":"sample output 1","content":"2\n\n$X$ becomes one of the following, with probability $1/6$ for each:\n\n*   $X = (1,1,1)$, for which the length of the longest increasing subsequence is $1$;\n*   $X = (1,1,2)$, for which the length of the longest increasing subsequence is $2$;\n*   $X = (1,1,3)$, for which the length of the longest increasing subsequence is $2$;\n*   $X = (1,2,1)$, for which the length of the longest increasing subsequence is $2$;\n*   $X = (1,2,2)$, for which the length of the longest increasing subsequence is $2$;\n*   $X = (1,2,3)$, for which the length of the longest increasing subsequence is $3$.\n\nThus, the expected value of the length of the longest increasing subsequence is $(1 + 2 + 2 + 2 + 2 + 3) / 6 \\equiv 2 \\pmod {1000000007}$."},{"iden":"sample input 2","content":"3\n2 1 2"},{"iden":"sample output 2","content":"500000005\n\n$X$ becomes one of the following, with probability $1/4$ for each:\n\n*   $X = (1,1,1)$, for which the length of the longest increasing subsequence is $1$;\n*   $X = (1,1,2)$, for which the length of the longest increasing subsequence is $2$;\n*   $X = (2,1,1)$, for which the length of the longest increasing subsequence is $1$;\n*   $X = (2,1,2)$, for which the length of the longest increasing subsequence is $2$.\n\nThus, the expected value of the length of the longest increasing subsequence is $(1 + 2 + 1 + 2) / 4 = 3 / 2$. Since $2 \\times 500000005 \\equiv 3 \\pmod {1000000007}$, we should print $500000005$."},{"iden":"sample input 3","content":"6\n8 6 5 10 9 14"},{"iden":"sample output 3","content":"959563502"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}