Practice on Toph

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

Switchblade of Thanos

By OnikJahanSagor · Limits 1s, 512 MB

We all know that Thanos “The Mad Titan“ had two adopted daughters, Gamora and Nebula. But did you know that he had one real daughter, Quanita? Thanos had a switchblade. His switchblade was special because it had two blades with equal weights. The weight of the switchblade was balanced indicating his vision to form a balanced universe. He gave it to Gamora, his favorite adopted daughter. But after the death of Gamora and Thanos, the switchblade was handed over to Nebula. Nebula didn’t want to keep it to her. So, when she found out that Thanos had a real daughter, she searched for her. After a tedious journey, she found the actual daughter of Thanos, Quanita. But because of the journey and being unused for a long time, the switchblade became unbalanced. Now, it’s Quanita’s job to make it balanced.

She has a sequence AA of NN metal plates in order which she can use to balance the switchblade. The weight of the ii-th plate is AiA_{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(1N100)N (1 \leq N \leq 100) the number of the metal plates.

The second line of the input will contain NN space separated integers A1,A2,A3,A4,,ANA_{1}, A_{2}, A_{3}, A_{4}, …, A_{N}(1Ai1000)(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 998244353998244353.

Sample

InputOutput
4
3 2 5 1
2

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

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

The other one is 3,2,13, 2, 1. If we split this subsequence after the first element, the sum of the both sides become equal as 3=2+13 = 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.

Discussion

Statistics


77% Solution Ratio

sh2018331053Earliest, 1M ago

S_SubrataFastest, 0.0s

S_SubrataLightest, 918 kB

rafi_1703076Shortest, 685B

Submit

Login to submit

Editorial

Notice that the maximum sum of all elements can be at most 10510^5105. So, we can easily use Dynamic...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.