Count IS for All Subsets

2 secs 1024 MB
bayashiko's icon bayashiko

問題文

長さ NN の整数列 A=(A1,A2,,AN)A=(A_1,A_2,\ldots,A_N) が与えられます。
集合 S={1,2,,N}S=\{1,2,\ldots,N\} の空でない部分集合 TT に対して、 f(T)f(T) を以下のように定義します。

  • TT の空でない部分集合 {x1,x2,,xk}(x1<x2<<xk)\{x_1,x_2,\ldots,x_k\} (x_1 < x_2 < \ldots < x_k) であって、 Ax1<Ax2<<AxkA_{x_1} < A_{x_2} < \ldots < A_{x_k} となるようなものの個数

TT として考えられるものは全部で 2N12^N-1 通りありますが、そのすべてに対する f(T)f(T) の和を 998244353998244353 で割った余りを求めてください。

  

制約

  • 1N20001\leq N \leq 2000
  • 1AiN1\leq A_i \leq N
  • 入力は全て整数   

入力

入力は以下の形式で標準入力から与えられます。

NN
A1 A2 ... ANA_1 \ A_2 \ ...\ A_N

  

出力

答えを出力してください。

  

入力例1

3
1 3 2

出力例1

16

f({1})=1({1})f(\{1\})=1 (\{1\})
f({2})=1({2})f(\{2\})=1 (\{2\})
f({3})=1({3})f(\{3\})=1 (\{3\})
f({1,2})=3({1},{2},{1,2})f(\{1,2\})=3 (\{1\},\{2\},\{1,2\})
f({1,3})=3({1},{3},{1,3})f(\{1,3\})=3 (\{1\},\{3\},\{1,3\})
f({2,3})=2({2},{3})f(\{2,3\})=2 (\{2\},\{3\})
f({1,2,3})=5({1},{2},{3},{1,2},{1,3})f(\{1,2,3\})=5 (\{1\},\{2\},\{3\},\{1,2\},\{1,3\})
と計算できるので答えは 1+1+1+3+3+2+5=161+1+1+3+3+2+5=16 です。

入力例2

16
8 4 11 2 6 11 9 1 2 1 10 10 7 8 13 1

出力例2

2197504

提出


Go (1.21)