Ecasdqina's page

home > problems

増加列(Judge ver.)

問題文

{1, 2, 3, 4, ..., N}を並び替えた順列pが与えられるので, 単調増加であるようなpの部分列の個数を求めてください.

ただしpの部分列とはpから1つ以上の要素を順序を保ったまま抜き出したものを言い, 単調増加とは任意の要素について $i\le j⇒p_i\le p_j$が成り立つことを言う。

入力

$N$

$p_1\ p_2\ \cdots\ p_{N-1}\ p_N$

出力

組合せの数を$10^9+7$で割った余りを1行で出力してください.

制約

$1\le N\le 100$

$1\le p_i\le N$

サンプル-1

入力

3

1 2 3

出力

7

説明

{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} の7パターンです.

サンプル-2

入力

3

3 2 1

出力

3

説明

{3}, {2}, {1}の3パターンです.

サンプル-2

入力

10

1 2 3 4 5 6 10 7 8 9

出力

575

Solver

Solver List