Syrjälän pizzeriassa voi valita pizzaan n erilaista täytettä. Jokaisella täytteellä on tietty hinta, ja pizzan kokonaishinta on kaikkien täytteiden hintojen summa. Mikä tahansa täyteyhdistelmä on mahdollinen.

Uolevin sukujuhliin tilattiin yksi kappale jokaista mahdollista pizzaa. Tehtäväsi on laskea, paljonko tilaus maksoi yhteensä.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: täytteiden määrä.

Seuraavalla rivillä on n kokonaislukua t_1,t_2,\ldots,t_n, jotka kuvaavat täytteiden hinnat.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: pizzojen yhteishinta. Koska luku voi olla hyvin suuri, tulosta se modulo 10^9+7.

Esimerkki

Syöte:

3
5 5 4

Tuloste:

56

Selitys: Erilaisia pizzoja on 8:

• ei täytettä (hinta 0)
• täyte 1 (hinta 5)
• täyte 2 (hinta 5)
• täyte 3 (hinta 4)
• täytteet 1+2 (hinta 10)
• täytteet 2+3 (hinta 9)
• täytteet 1+3 (hinta 9)
• kaikki täytteet (hinta 14)

Kun kaikki hinnat lasketaan yhteen, saadaan tulokseksi 56.

Osatehtävä 1 (16 pistettä)

• 1 \le n \le 10
• 1 \le t_i \le 100

Osatehtävä 2 (17 pistettä)

• 1 \le n \le 20
• 1 \le t_i \le 10^9

Osatehtävä 3 (67 pistettä)

• 1 \le n \le 10^5
• 1 \le t_i \le 10^9