{"problem":{"name":"A. World Cup","description":{"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 ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10177A"},"statements":[{"statement_type":"Markdown","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## Input\n\nThe 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.  .  . \n\n## Output\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[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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} $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10177A","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}