{"raw_statement":[{"iden":"statement","content":"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.\n\nA number $T$ $(1 < = T < = 10^5)$, the amount of test cases.\n\nFollowed by $T$ lines, each line has an integer $K$ $(1 < = K < = 5000000)$.\n\nFor each test case print a single integer $P$ $(0 < = P < 10^9 + 7)$, the probability that at least $K$ people survive Thano's snap.\n\nIn 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$.\n\n"},{"iden":"input","content":"A number $T$ $(1 < = T < = 10^5)$, the amount of test cases.Followed by $T$ lines, each line has an integer $K$ $(1 < = K < = 5000000)$."},{"iden":"output","content":"For each test case print a single integer $P$ $(0 < = P < 10^9 + 7)$, the probability that at least $K$ people survive Thano's snap."},{"iden":"note","content":"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$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N = 5 \\times 10^6 $.  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case, let $ K \\in \\mathbb{Z} $ satisfy $ 1 \\le K \\le N $.\n\n**Constraints**  \n1. $ 1 \\le T \\le 10^5 $  \n2. $ 1 \\le K \\le N $  \n\n**Objective**  \nFor each test case, compute the probability that at least $ K $ people survive, where each of the $ N $ people survives independently with probability $ \\frac{1}{2} $.  \n\nLet $ X \\sim \\text{Binomial}(N, \\frac{1}{2}) $.  \nCompute:  \n$$\nP_K = \\Pr(X \\ge K) = \\sum_{i=K}^{N} \\binom{N}{i} \\left(\\frac{1}{2}\\right)^N \\mod (10^9 + 7)\n$$  \n\nOutput $ P_K \\mod (10^9 + 7) $.","simple_statement":"Given 5 million people, each has a 50% chance to survive. For each test case with integer K, find the probability that at least K people survive, modulo 10^9 + 7.","has_page_source":false}