Pizzeria

• Time limit: 1.50 s
• Memory limit: 128 MB

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$