D. Антиматерия
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Яхуб неожиданно открыл секретную лабораторию. Там он нашел n устройств, выстроенных в линию и пронумерованных от 1 до n слева направо. Каждое устройство i (1 ≤ i ≤ n) может создать либо ai единиц материи, либо ai единиц антиматерии.

Яхуб хочет выбрать какой-то непрерывный подотрезок устройств в лаборатории, уточнить тип производства для каждого устройства подотрезка (производить материю или антиматерию) и, наконец, заснять подотрезок. Однако фото будет успешно, только если выделенные устройства произведут одинаковое количество материи и антиматерии (иначе, на фотографии будет лишняя материя или антиматерия).

Вас попросили вычислить количество различных способов, которыми Яхуб может успешно заснять фотографию. Одна фотография отлична от другой, если на ней запечатлен другой подотрезок или по крайней мере одно устройство подотрезка на одной фотографии производит материю, а на другой — антиматерию.

Входные данные

В первой строке содержится целое число n (1 ≤ n ≤ 1000). Во второй строке содержатся n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 1000).

Сумма a1 + a2 + ... + an не превосходит 10000.

Выходные данные

Выведите единственное целое число — количество способов, которыми Яхуб может снять фотографию по модулю 1000000007 (109 + 7).

Примеры
Входные данные
4
1 1 1 1
Выходные данные
12
Примечание

Возможные фотографии таковы: [1+, 2-], [1-, 2+], [2+, 3-], [2-, 3+], [3+, 4-], [3-, 4+], [1+, 2+, 3-, 4-], [1+, 2-, 3+, 4-], [1+, 2-, 3-, 4+], [1-, 2+, 3+, 4-], [1-, 2+, 3-, 4+] и [1-, 2-, 3+, 4+], где i +  означает, что i-ый элемент производит материю, а i -  означает, что i-ый элемент производит антиматерию.