+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- **دوره ۲۸ ایا** بعضی وقت‌ها خسته می‌شدند. **دوره ۱۰۲۸ ایا** بعد از فهمیدن این موضوع می‌خواهند آن برای تخریب وجهه **دوره ۲۸ ایا** استفاده کنند. **دوره ۲۸ ایا** در زمان خستگی همه دور هم جمع می‌شدند و فعالیت روزانه استاد بزرگ را تماشا می‌کردند. استاد بزرگ هر روز یک تکه چوب دارای $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}$ می‌باشد.