ملخی می‌خواهد از شاخه‌ی اول درختی به بالای آن برود. در این درخت $n$‌ شاخه وجود دارد و در هر شاخه مقدار صحیحی برگ موجود است. ملخ تمام برگ شاخه‌ای را که زمانی روی آن قرار بگیرد (و از جمله شاخه‌های اول و آخر) را می‌خورد. اما جادوگر بدجنسی ملخ را جادو کرده است به گونه‌ای که اگر در انتها مقدار برگی که ملخ خورده عددی فرد باشد، ملخ به سوسک مبدل می‌گردد. در ضمن ملخ فقط بین بعضی از شاخه‌ها می‌تواند بجهد و همیشه از شاخه پایین‌تر (با شماره کم‌تر) به شاخه‌ی بالاتر (با شماره‌ی بیش‌تر) می‌جهد.

برنامه‌ای بنویسید که تعداد مسیرهایی را که ملخ با حفظ شرایط و بدون سوسک شدن می‌تواند برای رسیدن به شاخه‌ی $n$‌ام طی کند را بیابد.

در سطر اول فایل ورودی مقدار $n$ $(n\leq 100)$ و در سطر دوم به ترتیب مقدار برگ موجود در هر شاخه داده شده است. در سطرهای بعدی در هر سطر دو عدد داده شده که نشان می‌دهد ملخ می‌تواند بین این دو شاخه بجهد. انتهای این سطرها با سطر $(00)$‌مشخص شده است.

جواب را در فایل خروجی بنویسید.

فرض کنید تمام اعداد ورودی از نوع Integer‌ هستند.