题目描述
Appu doesn't like maths.He was always intimidated by its calculations and stuff.To make matters worse,his Maths teacher is very strict.He gives him tough Home Work problems to him at the end of each chapter.If Appu fails to do the homework correctly,he punishes him.
Today Appu's teacher finished teaching him Set Theory,and he gave Appu the following problem:
" Lists are just like sets the only difference being that in lists a number can appear many time unlike in sets.For example {4,5,5} is a list,but not a set because 5 appears twice.But {4,5} is both a list and set.A list of size n has (2^n)-1 non-empty sublists. For example, {1,3,3} has 7 sublists : {1},{3},{3},{1,3},{3,3},1,3},{1,3,3} . Lets define sublist sum of a list as sum of all the elements in the sub-list. Lets denote sublist sums of a list S as SS[1],SS[2],SS[3]...... ,SS[ 2^n -1]. Lets also define a All Sublists Sum as ASS,
ASS= (2^SS[1])+(2^(SS[2]) ..... + 2^(SS[2^n -1]) . Now given a list S,find the ASS of that list. "
Looking at this statement, Appu was horrified.He has no clue whatsover on how to proceed.Can you help Appu from his punishment the next day in the class?
Input
The first line contains an integer N - the size of list S.Then next line contains N elements of list S.
Output
Output the (ASS of the list S)%(10^9+7)
Constraints
1 ≤ N ≤ 10^5
Each element of the list can be from 0 and 10^10 (inclusive)
SAMPLE INPUT
3
6 4 5
SAMPLE OUTPUT
36464
输入格式
见题面
输出格式
见题面
样例输入
1000
3683 31541 32962 19732 9292 17301 21242 6416 40745 22176 6121 40300 14201 43548 32031 303 30804 43487 15783 4598 33957 14688 7348 32500 33654 21093 17368 36171 5643 37847 17776 9325 35739 738 45408 45031 18038 16649 1446 25134 38824 7566 31785 19376 17466 13815 19678 14621 7302 1813 19219 41258 16500 42918 40109 16505 14010 7476 2675 36004 45322 36803 11680 31061 3892 7087 42443 38281 40088 43888 13415 45263 17806 45199 14639 1623 9014 34316 16243 32667 2480 1813 40276 18979 44731 30385 35484 25092 37860 4510 27448 49534 7664 39127 46946 11555 12566 39388 49836 2653 49627 13250 14267 17432 8448 28905 35406 33813 29573 1649 32831 32052 19813 23107 17383 30895 3491 19218 5987 7702 40079 49786 7235 47743 38912 20532 9297 17829 9919 9132 36833 9546 38733 1100 43329 13533 46356 28735 47345 25928 46735 30176 24332 16547 19634 41714 47442 39476 27283 19780 47177 17361 19565 20764 15103 24828 41295 24400 42657 17566 49883 29489 27111 38616 46940 36791 2148 43296 31877 15844 35575 28611 12371 9906 11510 32004 17971 25303 21479 45253 45082 35008 12614 30998 5771 44068 5825 13417 18467 14833 30982 34702 10674 24444 39669 7613 11235 41816 17260 43111 24011 2835 38074 36382 12740 49583 34737 30711 24885 22568 25963 36318 7575 4928 17315 29697 48996 39491 43113 33814 4324 40447 18515 31349 14890 24535 38961 26124 32702 6221 35587 6713 25407 23660 9446 38146 39594 10534 35208 14478 33101 27523 795 7027 32450 34461 3075 47797 23951 12540 31611 44626 2986 16477 25974 17875 41012 31287 10351 23713 3859 12289 46777 29265 35948 6222 33762 41893 16756 18970 6370 16208 46492 23516 39587 45293 24328 42661 43090 14630 5200 41052 9256 24537 23880 1581 8764 31243 49219 19114 4956 19429 31402 18084 15045 33701 40658 48807 25593 23765 17776 48314 39972 30619 38181 45910 25911 12508 38571 35352 27137 10122 42755 2744 1011 16635 20677 9774 14229 19895 28887 19184 5676 26640 3620 20720 26692 44277 19526 18636 18041 3653 16949 8012 34271 5129 20274 26534 33988 25196 28237 11124 35317 20992 13868 2679 3978 34544 12452 18206 20790 7690 3742 26465 681 7361 47185 27372 1637 16710 46007 36029 36715 29307 10392 20985 787 30665 47518 34774 5860 42107 45898 7529 13098 26117 10207 33427 27012 22659 17984 47801 46700 21725 40618 47381 45437 4154 41104 13425 37215 3463 49453 23929 32769 9845 44914 33556 6861 8783 18329 12721 889 30578 20249 30338 6694 46807 30116 57 35817 48100 14210 32517 19824 4827 46249 31613 8980 37352 45037 46194 40814 10842 20123 39935 37038 31388 23490 43898 40170 8170 22970 7411 38748 43218 37748 11793 6377 34216 28202 42193 32315 42411 24709 18490 47237 37309 102 6216 24661 11491 18761 31826 38684 38883 21760 25721 20270 45249 35970 26792 19771 8940 34202 24870 18509 38301 36662 24885 22516 31215 17078 21182 23625 8138 39672 20861 45447 39773 43428 36459 17615 28541 18284 6298 33775 40044 48370 20397 1644 34340 47188 21414 43279 47741 46283 11787 2393 49297 3024 24909 30511 20101 46090 20488 44590 2113 41348 6388 8238 1128 42846 25852 29668 27482 48502 13442 33877 46871 33838 35520 31210 47377 23286 40840 45117 35920 18979 13862 35216 22002 38770 32079 8454 1211 2566 19395 3324 10265 25783 11561 11392 34980 3764 7411 12461 2265 37205 46337 15488 37394 48209 13049 34771 21494 3889 46239 7413 22867 10100 8981 11220 15221 41059 19673 32784 9976 39067 2459 20240 31201 30371 47984 16181 486 21746 44993 2751 8950 7682 34590 46344 5890 47638 47466 27383 1526 10056 1147 40744 36508 10127 1963 18080 17537 37987 17215 27512 43406 19673 14104 24606 16395 28439 7138 16881 184 18483 35983 9134 26164 20572 21829 32053 18209 35646 25787 36087 12053 26933 26830 48560 3412 28793 32992 20948 33131 206 14812 26536 36231 28915 17494 2625 7353 40983 19505 23888 9465 21839 33021 35628 42410 21201 34032 10619 6846 9818 46705 18899 3103 39886 33810 6514 35030 16801 43813 18161 17007 8624 11048 3237 3890 28541 22213 27594 19524 41718 1482 45340 13556 854 30968 22318 22055 31351 32936 45252 41169 45992 14150 44271 35877 14312 17136 37259 31112 27300 5419 14470 35924 16466 17706 6165 11359 39919 33759 47234 47988 35240 42573 27895 2445 39892 212 24499 21243 49499 19751 28763 11842 252 39385 14071 14563 6520 1329 45675 33819 6747 26496 36094 39564 44202 42259 922 472 42369 14507 14811 43960 7080 42705 46404 13323 9269 37255 34565 8767 7005 29679 36961 7256 19063 1031 38171 41934 18711 197 42105 25457 26692 28198 31372 37245 36808 48646 37716 45528 13152 18878 39487 36583 27935 2243 49906 37203 39497 822 12321 46501 30501 49281 20108 15915 16663 8278 7849 35373 24826 49953 27181 1518 44502 24905 38762 47662 23550 42830 43189 3053 11707 49028 39636 39641 1270 5893 26843 40766 6714 5516 3618 3566 21148 40077 35833 37811 14707 43681 39535 39532 9985 16716 41049 4486 7972 46163 18499 31521 38992 11688 34573 698 27067 24208 40339 28336 46452 33533 35453 19518 5400 5422 23083 26548 45498 8915 30710 26556 18947 20244 16088 28931 3311 23488 49769 11282 19650 18267 42802 24993 46306 43727 25691 23372 34286 32381 18059 30738 32265 19863 255 37665 25284 39689 30564 37134 14956 11273 13689 33902 47868 46128 29185 1179 35968 45305 28812 21969 29923 37966 46962 26229 31692 39004 15952 15977 37736 363 13066 20000 20225 29672 24016 11861 19361 4579 48994 34316 32203 29034 34569 30071 41514 13753 47601 27481 9057 26412 15801 5332 14377 29114 47912 46068 18117 30215 28397 5852 30577 7814 42204 17154 37486 16219 29014 6846 37150 44359 7513 35704 23392 42081 15774 31257 22186 13374 25089 47594 39786 40890 2925 4162 36355 836 16582 4472 31051 11330 26675 27979 19143 18878 45132 6628 1449 40497 29825 4950 34855 37337 40653 24599 45770 6427 5855 17955 36152 47296 15548 42289 38185 34825 12803 24539 35660 45736 45362 33062 7065 22037 11041 26207 7266 22524 49187 8714 13021 29011 30015 47875 32700 20668 38825 28469 43446 11032 46423 97
样例输出
90767300