Sum of 2^Pi mod 1000000007 for all i where Pi is sum of numbers in ith subset of a set X I am stuck on a problem in which I have to print sum of 2Pi mod 1000000007 for all i where Pi  is sum of numbers in ith subset of a set X.

Length of set can be upto 100000.

Value of element in the range [0,1012].

Here's the link of the Problem.
Problem Statement

I could not find any approach other than Brute-Force which gives verdict TLE.

@Moderators,admins etc.
Before putting this question on hold or marking off-Topic or closed....
Please comment the reason so that I can know the reason and if possible reword it or ask on any other StackExchange Site.
I first posted it on codegolf.stackexchange.com and people(moderators) there have suggested me to post it here as it comes under algorithm category.

You can read about it here.

Programming Puzzles and Code golf

Thank You
If the set you're using is $X=\{x_1,x_2, \dotsc,x_n\}$, then the expression you want to evaluate is equivalent to
$$
(2^{x_1}+1)(2^{x_2}+1)\dotsm(2^{x_n}+1)\bmod{1000000007}
$$
This isn't too hard to prove; here's an example to help you see what's going on:

Suppose $X=\{a,b,c\}$. Then the subsets of $X$ are, obviously,
$$
\{\},\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}
$$
and the corresponding sums of elements in those subsets will be
$$
0,a,b,c,a+b,a+c,b+c,a+b+c
$$
leading to the sum
$$
2^0+2^a+2^b+2^c+2^{a+b}+2^{a+c}+2^{b+c}+2^{a+b+c}=(2^a+1)(2^b+1)(2^c+1)
$$
The general result can be established by a fairly simple induction proof.