AT_arc214_c [ARC214C] Divide into 4 Teams

There are $ N $ people numbered $ 1, \dots ,N $ . The **strength** of person $ i $ is $ P_i $ . Each person is assigned to one of the teams $ A,B,C,D $ to form four teams. There are $ 4^N $ ways to form teams; among these, find the number, modulo $ 998244353 $ , of formations that satisfy all of the following conditions. - Each of the teams $ A,B,C,D $ has at least one person. - The sum of the strengths of the people in team $ A $ equals the sum of the strengths of the people in team $ B $ . - The sum of the strengths of the people in team $ C $ equals the sum of the strengths of the people in team $ D $ .

The input is given from Standard Input in the following format: > $ N $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $

Output the number, modulo $ 998244353 $ , of formations that satisfy the conditions in the problem statement.

### Sample Explanation 1 The following eight team formations satisfy the conditions. Person $ 1 $ Person $ 2 $ Person $ 3 $ Person $ 4 $ Formation $ 1 $ ABCDFormation $ 2 $ BACDFormation $ 3 $ ABDCFormation $ 4 $ BADCFormation $ 5 $ CDABFormation $ 6 $ CDBAFormation $ 7 $ DCABFormation $ 8 $ DCBA ### Sample Explanation 2 No formations satisfy the conditions. ### Constraints - $ 4 \le N \le 500 $ - $ 1 \le P_i $ - $ \sum_{1 \le i \le N} P_i \le 10^5 $ - All input values are integers.