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

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

ورودی

در خط اول ورودی عدد $n$ آمده است. در خط بعد دنباله داده شده است. $$1 \le n \le 300\ 000$$

اعداد دنباله، نامنفی و حداکثر $10^9$ هستند.

خروجی

باقی‌مانده‌ی عدد نهایی پس از انجام این پروسه بر $10^9 + 7$ را چاپ کنید.

مثال

ورودی نمونه ۱

4
1 2 3 4

خروجی نمونه ۱

0

$$1, 2, 3, 4$$ $$1, 1, 1$$ $$0, 0$$ $$0$$

ورودی نمونه ۲

2
1 2

خروجی نمونه ۲

1

$$1, 2$$ $$1$$

ورودی نمونه ۳

2
2 1

خروجی نمونه ۳

1000000006

$$2, 1$$ $$-1$$