Sinulle annetaan taulukko, jossa on n kokonaislukua. Tehtäväsi on laskea yhteen jokaisen mahdollisen alitaulukon summa.

Esimerkiksi taulukon [1,2,3] alitaulukot ovat [1], [2], [3], [1,2], [2,3] ja [1,2,3]. Niistä muodostuu summa 1+2+3+3+5+6=20.

Koska vastaus voi olla suuri luku, ilmoita se modulo 10^9+7.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: taulukon koko.

Seuraavalla rivillä on n kokonaislukua x_1,x_2,\ldots,x_n: taulukon sisältö.

Tuloste

Tulosta yksi kokonaisluku: haluttu summa modulo 10^9+7.

Esimerkki

Syöte:

3
1 2 3

Tuloste:

20

Osatehtävä 1 (15 pistettä)

• 1 \le n \le 100
• 1 \le x_i \le 100

Osatehtävä 2 (85 pistettä)

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