• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

می‌خواهیم تمام نقاط صحیح محور مختصات را با \(n\) رنگ متفاوت، رنگ کنیم.

می‌دانیم طول تناوب رنگ \(i\) ام \(l_i\) است، به این معنی که اگر هر نقطه‌ای مانند \(x\) را با رنگ \(i\)ام رنگ کنیم، باید نقاط \(x+l_i\) و \(x-l_i\) نیز حتما به رنگ \(i\)ام باشند.

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

از آنجایی که جواب نهایی می‌تواند بسیار بزرگ باشد، کافی است باقی مانده‌ی پاسخ را بر \(10^9+7\) چاپ کنید.

ورودی

در اولین خط از ورودی مقدار \(n\) به شما داده شده است.

\[1 \le n \le 10^6\]

در خط بعدی \(n\) عدد آمده است که عدد \(i\)ام نمایانگر مقدار \(l_i\) است.

\[1 \le l_i \le 10^6\]

خروجی

در تنها خط خروجی باید تعداد روش‌های رنگ‌آمیزی محور مختصات را چاپ کنید.

مثال

ورودی نمونه ۱

3
1 1 1

خروجی نمونه ۱

3

ورودی نمونه ۲

4
1 2 4 4

خروجی نمونه ۲

26