{"problem":{"name":"Random LIS","description":{"content":"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 distri","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc104_e"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 6$\n*   $1 \\leq A_i \\leq 10^9$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\cdots$ $A_N$\n\n[samples]\n\n## Notes\n\nA 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$.","is_translate":false,"language":"English"}],"meta":{"iden":"arc104_e","tags":[],"sample_group":[["3\n1 2 3","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}$."],["3\n2 1 2","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$."],["6\n8 6 5 10 9 14","959563502"]],"created_at":"2026-03-03 11:01:14"}}