Однажды Вася взял бумажную полоску из n клеток (высота полоски равна 1 клетке) и в каждой клетке написал целое число, возможно отрицательное. Ему стало интересно, сколько существует способов разрезать полоску на три части так, что суммы чисел в каждой из частей равны между собой, и в каждой части содержится целое положительное число клеток. Помогите Васе решить эту задачу.
В первой строке входных данных содержится целое число n (1 ≤ n ≤ 105) — количество клеток в полоске. Во второй строке содержится n чисел, разделенных пробелами — числа, записанные в клетках полоски. Эти числа целые и не превосходят по модулю 10000.
Выведите число способов разрезать полоску на три непустые части так, что суммы чисел в каждой из частей равны между собой. Не забудьте, что разрезать полоску разрешается только по границам клеток.
4
1 2 3 3
1
5
1 2 3 4 5
0
