AT_arc104_e [ARC104E] Random LIS

Description

[problemUrl]: https://atcoder.jp/contests/arc104/tasks/arc104_e 長さ $ N $ の整数列 $ A_1,\ A_2,\ \cdots,\ A_N $ が与えられます。 同じく長さ $ N $ の整数列 $ X $ は、 各 $ i\ (1\ \leq\ i\ \leq\ N) $ について独立に、 $ 1\ \leq\ X_i\ \leq\ A_i $ を満たす整数の一様分布からランダムに選ばれます。 このとき、$ X $ の最長増加部分列の長さの期待値を mod $ 1000000007 $ で計算してください。 より正確には、期待値が有理数、つまりある既約分数 $ \frac{P}{Q} $ で表せること、更に $ R\ \times\ Q\ \equiv\ P\ \pmod\ {1000000007} $, $ 0\ \leq\ R\

Input Format

N/A

Output Format

N/A

Explanation/Hint

### 注釈 列 $ X $ の部分列とは $ X $ の要素をいくつか抜き出して元の順に並べてできる列のことを指し、また、列 $ X $ の最長増加部分列とは、$ X $ の狭義単調増加な部分列の中で列の長さが最大のものを指します。 ### 制約 - $ 1\ \leq\ N\ \leq\ 6 $ - $ 1\ \leq\ A_i\ \leq\ 10^9 $ - 入力は全て整数である ### Sample Explanation 1 $ X $ はそれぞれ確率 $ 1/6 $ で次のいずれかになります。 - $ X\ =\ (1,1,1) $ のとき、最長増加部分列の長さは $ 1 $ です。 - $ X\ =\ (1,1,2) $ のとき、最長増加部分列の長さは $ 2 $ です。 - $ X\ =\ (1,1,3) $ のとき、最長増加部分列の長さは $ 2 $ です。 - $ X\ =\ (1,2,1) $ のとき、最長増加部分列の長さは $ 2 $ です。 - $ X\ =\ (1,2,2) $ のとき、最長増加部分列の長さは $ 2 $ です。 - $ X\ =\ (1,2,3) $ のとき、最長増加部分列の長さは $ 3 $ です。 よって、最長増加部分列の長さの期待値は $ (1\ +\ 2\ +\ 2\ +\ 2\ +\ 2\ +\ 3)\ /\ 6\ \equiv\ 2\ \pmod\ {1000000007} $ です。 ### Sample Explanation 2 $ X $ はそれぞれ確率 $ 1/4 $ で次のいずれかになります。 - $ X\ =\ (1,1,1) $ のとき、最長増加部分列の長さは $ 1 $ です。 - $ X\ =\ (1,1,2) $ のとき、最長増加部分列の長さは $ 2 $ です。 - $ X\ =\ (2,1,1) $ のとき、最長増加部分列の長さは $ 1 $ です。 - $ X\ =\ (2,1,2) $ のとき、最長増加部分列の長さは $ 2 $ です。 よって、最長増加部分列の長さの期待値は $ (1\ +\ 2\ +\ 1\ +\ 2)\ /\ 4\ =\ 3\ /\ 2 $ ですが、$ 2\ \times\ 500000005\ \equiv\ 3\ \pmod\ {1000000007} $ であるので、$ 500000005 $ を出力してください。