Боб амттай бүхэнд дуртай. Түүний дуртай шоколад ширхэг ширхэгээр хуваагдаж болохоор байдаг ба ширхэг бүр самар агуулж болно. Боб хайрцаг шоколадаа хэсэг бүрт яг нэг самар байхаар хуваахыг хүсдэг ба хуваах шугам нь хоёр хөрш ширхэгийн голоор явна.

Та Боб шоколадыг хэдэн янзаар хувааж болохыг олно. Хэрвээ шоколадны хуваагдсан ширхэгүүдийн тоо нь адилхан ч байрлал нь өөр байвал хоёр ялгаатай тохиолдол гэж үзнэ.

Хэрвээ Боб шоколадыг хугалахгүй бол хайрцаг шоколад бүтнээрээ ганцхан самартай нэг хэсэг болно. Please note, that if Bob doesn't make any breaks, all the bar will form one piece and it still has to have exactly one nut.

Оролт

Эхний мөрөнд хайрцаг шоколадны ширхэгийн тоо $n$ ($1 ≤ n ≤ 100$) байна.

Хоёр дахь мөрөнд $n$ ширхэг бүхэл тоон утгууд $a_{i}$ ($0 ≤ a_{i} ≤ 1$) байх ба хэрвээ $0$ байвал харгалзах ширхэг шоколад нь самаргүй $1$ байвал самартай болно.

Гаралт

Хэсэг бүр яг ганц самартай байх хэсгүүдэд шоколадыг хэдэн янзаар хувааж болох тоог олж хэвлэ.

Эхний жишээн дээр ганцхан самар байгаа учраас хариулт $1$-тэй тэнцүү. Боб шоколадаа хугалахгүй.

Хоёр дахь жишээн дээр та шоколадыг дөрвөн янзаар хугалж болно:

$10|10|1$

$1|010|1$

$10|1|01$

$1|01|01$