{"raw_statement":[{"iden":"statement","content":"The 2018 World Cup will be hosted in Russia. 32 national teams will be divided into 8 groups. Each group consists of 4 teams. In group matches, each pair (unordered) of teams in the group will have a match. Top 2 teams with the highest score in each group will advance to eighth-finals. Winners of each eighth-final will advance to quarter-finals. Then, the winners of each quarter-final will advance to semi-finals. Eventually, the World Champion will be the winner of the World Final which is played between the two winners of the semi-finals.\n\nEach match is labeled with a match ID sequenced from 1 to 63, with group matches followed by eighth-final matches followed by quarter-final matches followed by semi-finals matches and finally the final match.\n\n_Zhuojie_ is going to watch the 2018 World Cup. Since the World Champion of ACM-ICPC is very rich, he decides to spend 0.01% of his daily salary to buy tickets. However, there are only match IDs on the tickets and the prices are missing. Can you calculate how much _Google_ pays _Zhuojie_ every workday? Note that _Zhuojie_ can buy multiple tickets for one match.\n\nThe input starts with one line containing exactly one integer T, the number of test cases.\n\nEach test case contains 3 lines. The first line contains 5 integers, indicating the ticket price for group match, eighth-final match, quarter-final match, semi-final match and the final match. The second line contains one integer N, the number of tickets _Zhuojie_ buys. The third line contains N integers, each indicating the match ID on the ticket.\n\nFor each test case, output one line containing \"_Case #x: y_\" where _x_ is the test case number (starting from 1) and _y_ is daily salary of _Zhuojie_.\n\n"},{"iden":"input","content":"The input starts with one line containing exactly one integer T, the number of test cases.Each test case contains 3 lines. The first line contains 5 integers, indicating the ticket price for group match, eighth-final match, quarter-final match, semi-final match and the final match. The second line contains one integer N, the number of tickets _Zhuojie_ buys. The third line contains N integers, each indicating the match ID on the ticket.  1 ≤ T ≤ 100.  1 ≤ N ≤ 105.  .  . "},{"iden":"output","content":"For each test case, output one line containing \"_Case #x: y_\" where _x_ is the test case number (starting from 1) and _y_ is daily salary of _Zhuojie_."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $, let $ n_k \\in \\mathbb{Z} $ and $ m_k \\in \\mathbb{Z}_{\\geq 0} $ denote the target position and time in seconds, respectively.\n\n**Constraints**  \n1. $ 1 \\leq T \\leq 10^5 $  \n2. $ -2 \\times 10^5 \\leq n_k \\leq 2 \\times 10^5 $  \n3. $ 0 \\leq m_k \\leq 2 \\times 10^5 $\n\n**Objective**  \nFor each test case $ k $, compute the probability $ P_k $ that a symmetric random walk starting at 0 reaches position $ n_k $ after exactly $ m_k $ steps, where at each step the walker moves $ +1 $ or $ -1 $ with equal probability $ \\frac{1}{2} $.  \n\nThe probability is $ P_k = \\frac{\\binom{m_k}{\\frac{m_k + n_k}{2}}}{2^{m_k}} $ if $ m_k \\geq |n_k| $ and $ m_k + n_k $ is even; otherwise $ P_k = 0 $.  \n\nOutput $ z_k \\equiv P_k \\pmod{10^9 + 7} $, where $ z_k \\in [0, 10^9 + 6] $, interpreted as $ z_k \\equiv p \\cdot q^{-1} \\pmod{10^9 + 7} $ for irreducible fraction $ \\frac{p}{q} $.","simple_statement":"Conan starts at position 0. Each second, he moves left or right by 1 with equal chance. After m seconds, what’s the probability he’s at position n? Output the answer modulo 10^9+7.","has_page_source":false}