- Time limit: 1.50 s
- Memory limit: 128 MB
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)
Osatehtävä 1 (16 pistettä)
- $1 \le n \le 10$
- $1 \le t_i \le 100$
- $1 \le n \le 20$
- $1 \le t_i \le 10^9$
- $1 \le n \le 10^5$
- $1 \le t_i \le 10^9$