AT_arc104_f [ARC104F] Visibility Sequence

[problemUrl]: https://atcoder.jp/contests/arc104/tasks/arc104_f 一列に並んだ $ N $ 棟のビルが建設中であり、ビルには左から順番に $ 1,\ 2,\ \ldots,\ N $ の番号がついています。 長さ $ N $ の整数列 $ X $ が与えられ、ビル $ i $ の高さ $ H_i $ は、$ 1 $ 以上 $ X_i $ 以下の整数のいずれかにすることができます。 $ 1\ \leq\ i\ \leq\ N $ に対して、$ P_i $ を次のように定めます。 - $ H_j\ >\ H_i $ を満たすような整数 $ j\ (1\ \leq\ j\

入力は以下の形式で標準入力から与えられる。 > $ N $ $ X_1 $ $ X_2 $ $ \cdots $ $ X_N $

全てのビルの高さの組み合わせを考えるとき、 $ P $ としてありうる整数列の個数を $ 1000000007 $ で割った余りを出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 100 $ - $ 1\ \leq\ X_i\ \leq\ 10^5 $ - 入力は全て整数である ### Sample Explanation 1 $ H $ としては、次の $ 6 $ 通りが考えられます。 - $ H\ =\ (1,\ 1,\ 1) $ のとき、$ P $ は $ (-1,\ -1,\ -1) $ である - $ H\ =\ (1,\ 2,\ 1) $ のとき、$ P $ は $ (-1,\ -1,\ 2) $ である - $ H\ =\ (2,\ 1,\ 1) $ のとき、$ P $ は $ (-1,\ 1,\ 1) $ である - $ H\ =\ (2,\ 2,\ 1) $ のとき、$ P $ は $ (-1,\ -1,\ 2) $ である - $ H\ =\ (3,\ 1,\ 1) $ のとき、$ P $ は $ (-1,\ 1,\ 1) $ である - $ H\ =\ (3,\ 2,\ 1) $ のとき、$ P $ は $ (-1,\ 1,\ 2) $ である よって、$ P $ としてありうる整数列は $ (-1,\ -1,\ -1),\ (-1,\ -1,\ 2),\ (-1,\ 1,\ 1),\ (-1,\ 1,\ 2) $ の $ 4 $ 個です。 ### Sample Explanation 2 $ H $ としては、次の $ 2 $ 通りが考えられます。 - $ H\ =\ (1,\ 1,\ 1) $ のとき、$ P $ は $ (-1,\ -1,\ -1) $ である - $ H\ =\ (1,\ 1,\ 2) $ のとき、$ P $ は $ (-1,\ -1,\ -1) $ である よって、$ P $ としてありうる整数列は $ 1 $ 個です。