問題文
長さ N の整数列 A=(A1,A2,…,AN) が与えられます。
集合 S={1,2,…,N} の空でない部分集合 T に対して、 f(T) を以下のように定義します。
- T の空でない部分集合 {x1,x2,…,xk}(x1<x2<…<xk) であって、 Ax1<Ax2<…<Axk となるようなものの個数
T として考えられるものは全部で 2N−1 通りありますが、そのすべてに対する f(T) の和を 998244353 で割った余りを求めてください。
制約
- 1≤N≤2000
- 1≤Ai≤N
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます。
出力
答えを出力してください。
入力例1
出力例1
f({1})=1({1})
f({2})=1({2})
f({3})=1({3})
f({1,2})=3({1},{2},{1,2})
f({1,3})=3({1},{3},{1,3})
f({2,3})=2({2},{3})
f({1,2,3})=5({1},{2},{3},{1,2},{1,3})
と計算できるので答えは 1+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