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

---

دوره ۲۸ ایا بعضی وقت‌ها خسته می‌شدند. دوره ۱۰۲۸ ایا بعد از فهمیدن این موضوع می‌خواهند آن برای تخریب وجهه دوره ۲۸ ایا استفاده کنند. دوره ۲۸ ایا در زمان خستگی همه دور هم جمع می‌شدند و فعالیت روزانه استاد بزرگ را تماشا می‌کردند.

استاد بزرگ هر روز یک تکه چوب دارای $n$ مربع به هم چسبیده تهیه می‌کرد و در خانه $i$ ام آن عدد $a_i$ را می‌نوشت. پس از تهیه چوب استاد عملیات زیر را روی تمام مرز‌‌های مربع‌های متوالی انجام می‌داد ($n-1$ مرز داریم).

استاد با ذکر غوودا ضربه‌‌ای محکم به مرز می‌زد که این ضربه به احتمال $\frac{1}{2}$ چوب را می‌شکاند و به احتمال $\frac{1}{2}$ نمی‌شکاند (‌استاد در دوران پیری به سر می‌برد به همین دلیل بعضی وقت‌ها چوب نمی‌شکست).

آنگاه دوره ۲۸ ایا مات و مبهوت از مهارت استاد و به نشانه احترام جمع اعداد روی هر تکه چوب باقی‌مانده را بر سردر شاز نصب می‌کردند (برای مثال اگر $n = 3$ و اعداد روی تکه‌ها به ترتیب $17\ , 2\ , 3\ $ بودند و ضربه‌ی استاد مرز بین اولین تکه و دومین تکه را نمی‌شکاند ولی مرز بین دومین تکه و سومین را می‌شکاند، دوره ۲۸ ایا اعداد $5\ ,17\ $ را بر سر در شاز نصب می‌کردند).

دوره ۱۰۲۸ ایا برای اثبات خفونت خود می‌خواهند امیدریاضی تعداد اعداد متفاوتی که سر در شاز نصب می‌شود را بیابند (برای مثال تعداد اعضای متفاوت مجموعه‌ی ${7, 1, 2, 7, 3, 5, 1, 1}$ برابر $5$ است).

ثابت می‌شود که جواب مورد نظر را می توان به صورت کسر $\frac{P}{Q}$ نشان داد (که قابل ساده کردن نیست). از شما خواسته شده که $P.Q^{-1}$ را در پیمانه‌ $10^9+7$ خروجی دهید.

ورودی

در خط اول ورودی عدد $n$ داده می‌شود. سپس در خط بعدی $n$ عدد طبیعی می‌آیند که $i$ امین آنها $a_i$ می‌باشد. $$1 \le n \le 500 $$ $$-10^{15} \le a_i \le 10^{15}$$

خروجی

امیدریاضی تعداد اعداد متفاوت نصب شده در سردر را به فرم $P.Q^{-1}$ در پیمانه $10^9+7$ خروجی دهید.

مثال

ورودی نمونه ۱

2
-77 14   

خروجی نمونه ۱

500000005

به احتمال $\frac{1}{2}$ مجموعه ، ${-63}$

به احتمال $\frac{1}{2}$ مجموعه ، ${-77,14}$

بر سردر شاز نوشته می‌شوند پس جواب مسئله $\frac{1+2}{2}$ می‌باشد.

ورودی نمونه ۲

3
1 2 3

خروجی نمونه ۲

750000007

به احتمال $\frac{1}{4}$ مجموعه ، ${6}$

به احتمال $\frac{1}{4}$ مجموعه ، ${1,5}$

به احتمال $\frac{1}{4}$ مجموعه ، ${3,3}$

به احتمال $\frac{1}{4}$ مجموعه ، ${1,2,3}$

بر سر در شاز نوشته می‌شوند پس جواب مسئله $\frac{1+2+1+3}{4}$ می‌باشد.