# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

By OnikJahanSagor · Limits 1s, 512 MB

She has a sequence $A$ of $N$ metal plates in order which she can use to balance the switchblade. The weight of the $i$-th plate is $A_{i}$. The balancing task is not easy at all. She has to choose a non-empty sub-sequence of the metal plates. Then she will divide this sub-sequence into two non-empty consecutive parts in such a way that the sum of the weights of each part is equal. She will use the metals of the first part on one blade and the other part on another thus making the switchblade balanced. But not all the sub-sequences can be split into two parts like this. Now, Quanita is interested in how many ways she can choose a non-empty sub-sequence so that it can be split into two non-empty consecutive parts with an equal sum of weights. Help Quanita to find what she desires.

## Input

The first line of the input will contain an integer $N (1 \leq N \leq 100)$ the number of the metal plates.

The second line of the input will contain $N$ space separated integers $A_{1}, A_{2}, A_{3}, A_{4}, …, A_{N}$$(1 \leq A_{i} \leq 1000)$the weights of the metal plates.

## Output

Print an integer, the number of ways Quanita can choose a non-empty subsequence so that it can be split into two non-empty consecutive parts with an equal sum of weights as described above. As the number of such subsequence can be very large, print it modulo $998244353$.

## Sample

InputOutput
4
3 2 5 1

2


In the sample above, there can be two such subsequences.

One is $3, 2, 5$. If we split this subsequence after the second element, the sum of the both sides become equal as $3+2=5$.

The other one is $3, 2, 1$. If we split this subsequence after the first element, the sum of the both sides become equal as $3 = 2 + 1$.

A subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the elements.

Two subsequences are called different if they have at least one element from a different index than the other one.

### Statistics

77% Solution Ratio

sh2018331053Earliest, 1M ago

S_SubrataFastest, 0.0s

S_SubrataLightest, 918 kB

rafi_1703076Shortest, 685B