CSES - Putka Open 2015 – 4/6 - Pizzeria
  • Time limit: 1.50 s
  • Memory limit: 128 MB

Syrjälän pizzeriassa voi valita pizzaan nn 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 nn: täytteiden määrä.

Seuraavalla rivillä on nn kokonaislukua t1,t2,,tnt_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 109+710^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ä)

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

Osatehtävä 2 (17 pistettä)

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

Osatehtävä 3 (67 pistettä)

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