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 of metal plates in order which she can use to balance the switchblade. The weight of the -th plate is . 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.
The first line of the input will contain an integer the number of the metal plates.
The second line of the input will contain space separated integers the weights of the metal plates.
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 .
4 3 2 5 1
In the sample above, there can be two such subsequences.
One is . If we split this subsequence after the second element, the sum of the both sides become equal as .
The other one is . If we split this subsequence after the first element, the sum of the both sides become equal as .
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.
Login to submit
Notice that the maximum sum of all elements can be at most 10510^5105. So, we can easily use Dynamic...