D. Сөрөг масс

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Яхуб санамсаргүйгээр нэгэн нууц лаборатори илрүүлжээ. Тэр лаборатори дотор зүүнээс баруун тийш $1$-ээс $n$ хүртэл дугаарлагдсан $n$ ширхэг төхөөрөмж олсон байна. $i$ дүгээр $(1 ≤ i ≤ n)$ төхөөрөмж бүр нь $a_{i}$ хэмжээтэй эерэг масс, эсвэл $a_{i}$ хэмжээтэй сөрөг масс үүсгэж чадна.

Яхуб лабораторийн төхөөрөмжүүдийн зарим нэг үргэлжилсэн дэд массивыг сонгоод, тэдний тус бүрийнх нь үйлдвэрлэлийн горимыг (эерэг масс эсвэл сөрөг масс гаргах) зааж өгөөд, эцэст нь үүнийхээ зургийг авахыг хүсчээ. Гэхдээ сонгосон дэд массивын үйлдвэрлэсэн эерэг масс болон сөрөг массын хэмжээ тэнцүү тохиолдолд энэ нь боломжтой ба, тэнцэхгүй бол зураг амжилтгүй болж байлаа.

Та Яхуб хэдэн аргаар амжилттай зураг авч чадахыг тооцоолох хэрэгтэй. Төхөөрөмжүүдийн массив нь ялгаатай юм уу, ижил массивын ядаж нэг төхөөрөмж өөр өөр масс (нэгд нь эерэг масс, нөгөөд нь сөрөг масс) ялгаруулсан бол эдгээрийг ялгаатай зураг гэж үзнэ.

Оролт

Эхний мөр нь $n$ $(1 ≤ n ≤ 1000)$ бүхэл тоог агуулна. Хоёр дахь мөр нь $n$ ширхэг $a_{1}$, $a_{2}$, ..., $a_{n}$ $(1 ≤ a_{i} ≤ 1000)$ бүхэл тоонуудыг агуулна.

$a_{1} + a_{2} + ... + a_{n}$ нийлбэр $10000$-аас хэтрэхгүй.

Гаралт

Яхубын зураг авч болох аргуудын тоог ($10^{9}+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$-р элемент сөрөг масс ялгаруулдаг гэсэн утгатай.

Сэтгэгдлүүдийг ачааллаж байна...