AT_arc214_c [ARC214C] Divide into 4 Teams

$ 1, \dots ,N $ の番号がついた $ N $ 人の人がいます。人 $ i $ の**強さ**は $ P_i $ です。 各人を $ A,B,C,D $ のいずれかのチームに割り当てることで、 $ 4 $ つのチームにチーム分けをします。チーム分けの方法は $ 4^N $ 通りありますが、このうち以下の条件を全て満たすチーム分けの個数を $ 998244353 $ で割った余りを求めて下さい。 - $ A,B,C,D $ のどのチームにも $ 1 $ 人以上所属する。 - チーム $ A $ に所属する人の強さの和とチーム $ B $ に所属する人の強さの和が等しい。 - チーム $ C $ に所属する人の強さの和とチーム $ D $ に所属する人の強さの和が等しい。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $

問題文中の条件を満たすチーム分けの個数を $ 998244353 $ で割った余りを出力せよ。

### Sample Explanation 1 以下の $ 8 $ 通りのチーム分けが条件を満たします。 人 $ 1 $ 人 $ 2 $ 人 $ 3 $ 人 $ 4 $ チーム分け $ 1 $ ABCDチーム分け $ 2 $ BACDチーム分け $ 3 $ ABDCチーム分け $ 4 $ BADCチーム分け $ 5 $ CDABチーム分け $ 6 $ CDBAチーム分け $ 7 $ DCABチーム分け $ 8 $ DCBA ### Sample Explanation 2 条件を満たすチーム分けが存在しません。 ### Constraints - $ 4 \le N \le 500 $ - $ 1 \le P_i $ - $ \sum_{1 \le i \le N} P_i \le 10^5 $ - 入力される値は全て整数