406437: GYM102409 I Thanos's snap
Description
The city of Diegopolis has been growing to the point of reaching exactly 5 million people (making it 74th most populated city in the world), but to Diego's surprise (Diego is the mayor of Diegopolis), Thanos is about to snap his fingers and reduce the universe's population in approximately half. Because of this Diego wants to know what is the probability that at least K of his people survive Thanos's snap, since this number can be quite small make sure you print it modulo $$$10^9+7$$$. You should assume that any person has exactly 50% chance of surviving Thanos's snap.
InputA number $$$T$$$ $$$(1<=T<=10^5)$$$, the amount of test cases.
Followed by $$$T$$$ lines, each line has an integer $$$K$$$ $$$(1<=K<=5000000)$$$.
OutputFor each test case print a single integer $$$P$$$ $$$(0<=P<10^9+7)$$$, the probability that at least $$$K$$$ people survive Thano's snap.
ExampleInput2 0 5000000Output
1 195206359Note
In the sample test case there is a 100% chance that at least 0 people survive while the chances of all 5 million Diegopolians surviving is $$$\frac{1}{2^{5000000}} \equiv 195206359 \mod 10^9+7$$$.