+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- دزدان این روزها به خلاقیت والایی رسیدند و روی به دزدیدن آجرهای دیوار ملت آوردند! اما از آنجا که خلاقانه کار می‌کنند، قبل از هر عملیات برنامه ریزی‌های لازم برای برداشتن آجرها را به عمل می‌آورند. (آجرها به شکل ستون های متصل به هم قرار دارند.) آن‌ها پس از انتخاب یک دیوار ابتدا $n$ که همان تعداد ستون‌ها هست را بدست می‌آورند و سپس ارتفاع هر ستون ($h_i$) را بدست می‌آورند. (ارتفاع همان تعداد آجر هر ستون است.) بعد از شمارش آجرها را از بالا و به شکل مستطیل‌های متصل به هم برمی‌دارند (یعنی هر آجر برداشته شده باید همسایه ضلعی حداقل یک آجر دیگر باشد). از آنجا که این افراد عادل و انسان دوست هستند، حتما پایین ترین آجر را باقی میگذراند تا فرآیند بازسازی دیوار برایتان آسان تر شود! سبحان که فردی کنجکاو است از نقشه این دزدان با خبر شد و می‌خواهد تعداد تمام حالت‌های برداشتن آجرها از روی دیوار همسایه‌های خود را بررسی کنید. از آنجایی که برخی همسایه ها دیوارهای بسیار مرتفع و عریضی دارند، باقی مانده کل حالات به عدد $10^9+7$ را نمایش دهید. # ورودی خط اول شامل عدد طبیعی $n$ است. $$1 \le n \le 10^6 $$ خط دوم شامل n عدد با فاصله از هم $h_1, h_2, ..., h_n $ $$1 \le h_i \le 10^9$$ که $h_i$ برابر ارتفاع ستون i-ام است. # خروجی خروجی برنامه حاصل باقی مانده تعداد کل حالات گرفتن آجرها بر عدد $10^9+7$ می‌باشد. # مثال ## ورودی نمونه ۱ ``` 1 1 ``` ## خروجی نمونه ۱ ``` 0 ``` از آنجایی که دزدان منصف اند، نمیتوانند از پایین ترین سطر بردارند، پس هیچ حالتی وجود ندارد. ## ورودی نمونه ۲ ``` 3 3 2 3 ``` ## خروجی نمونه ۲ ``` 8 ``` تمام حالات در تصویر زیر نمایش داده شده‌ است.