13029번 - 홍준이와 반물질

문제

홍준이에게는 N개의 물질이 일렬로 나열되어 있다 각 물질의 양은 자연수로 표현된다.

홍준이는 연속한 부분 물질들을 선택해 마법을 부리려고 한다. 성공적으로 마법을 부리기 위해서는 선택한 물질 중 일부를 반물질로 바꾸어서 물질의 양의 합과 반물질의 양의 합이 같아야 한다. 홍준이는 아무 물질을 선택하지 않았을 때에는 마법을 부릴 수 없다. 따라서 최소한 2개 이상의 연속한 물질들을 선택해야 한다. 물질들에 대한 정보가 주어졌을 때, 홍준이가 성공적으로 마법을 부릴 수 있는 경우의 수를 출력하시오.

입력

첫째 줄에 물질의 개수 N(1 ≤ N ≤ 1000)가 주어진다.

둘째 줄에 i번째 물질의 양을 나타내는 a(i) (1 ≤ a(i) ≤ 10000)가 공백을 구분으로 주어진다.

모든 물질의 양의 합은 10000을 넘지 않는다.

출력

홍준이가 성공적으로 마법을 부릴 수 있는 경우의 수를 10⁹+7로 나눈 나머지를 출력한다.

제한

힌트