D. Сережа ба Кино театр

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

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

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

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

Сережагийн хот дахь кино театрын танхим нь нэг эгнээтэй ба энэ эгнээндээ $n$ суудалтай. Суудал бүрийн баруун зүүн талд тухайн суудалд суусан хүнд зориулагдсан тавиур байдаг. Дурын 2 хөрш суудал дундаа нэг л тавиуртай. Доорх зураг нь $n=4$ үе дэх суудлууд болон тавиуруудын байдлыг харуулж байна.

Өнөдөөр "Dry Hard" киноны нээлт болж байгаа ба бүх суудлын билет дуусжээ.Кино танхим руу орохдоо хүмүүс заавал нэг нэгээрээ ордог. Үзэгч танхимд орж суудлаа эзлээд шууд л өөрийн баруун болон зүүн тал дахь тавиурт өөрийн юмыг тавьж өөрийн болгодог. Хэрвээ тухайн хүний баруун ба зүүн тал дахь тавиурууд аль аль нь хоосон бус байвал тэр хүн ундууцаж кино театрыг орхин гардаг.

Хүмүүс ихэд тогтворгүй ба ямар дарааллаар танхимд хүрэлцэн ирэхийг нь таамаглахад тун хүнд. Зарим суудлын хувьд Сережа энэ суудалд суух хүн хэддүгээрт орж ирэхийг нь мэддэг. Харин бусад хүмүүсийн хувьд ямар ч дарааллаар орж ирж болно.

Программис ба математикчийнхаа хувьд Сережа танхимд орж ирэх хүмүүсээс хэн нь ч ундууцахгүй байхаар хэчнээн янзаар орж ирж болохыг мэдэхийг хүсчээ? Хариу том тоо гарч болох тул $10^9+7$ модулиар жишч хариуг гарга.

Оролт

Эхний мөр $n (1\le n\le 10^5)$. 2 дахь мөрөнд $n$ бүхэл тоо өгөгдөнө. $i$-дэх тоо нь $i$-р суудалд суух хүн хэддүгээрт орж ирэхийг илтгэнэ.Хэрвээ 0 байвал хэддүгээрт ч орж ирнэ болно гэсэн үг. 2 дахь мөрөн дэх эерэг бүхэл тоонууд бүгд өөр ялгаатай байна.

Гаралт

Нийт боломжийн тоог $1000000007 (10^9+7)$ тоонд хуваахад гарах үлдэгдлийг хэвлэ.

Орчуулсан: Төрбат

Жишээ тэстүүд

Оролт
11
0 0 0 0 0 0 0 0 0 0 0
Гаралт
1024
Оролт
6
0 3 1 0 0 0
Гаралт
3
Сэтгэгдлүүдийг ачааллаж байна...