{"problem":{"name":"L. Lost In The Echo","description":{"content":"Charles enjoys learning. He often goes to the website Wikipedia to study computer science. Just now Charles seriously studied a series of expressions, in which algebraic expression has a great influen","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":8000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10211L"},"statements":[{"statement_type":"Markdown","content":"Charles enjoys learning. He often goes to the website Wikipedia to study computer science. Just now Charles seriously studied a series of expressions, in which algebraic expression has a great influence on him.\n\nHe is curious about how many different algebraic expressions that can be built up from n distinct variables, elementary arithmetic operations (addition, subtraction, multiplication and division), and brackets such that each variable appears exactly once and each operation is after a variable or a pair of brackets. Can you help him calculate the answer in modulo (109 + 7)?\n\nTwo algebraic expressions in this problem are considered as equivalent if and only if they can be simplified as the same rational expression. For example, assuming a, b, c and d are variables, (a - d) / (b - c) is equivalent to (d - a) / (c - b), a / (b - c) * d is equivalent to a / ((b - c) / d), but a / b + c / d is not equivalent to d / c + b / a.\n\nThe first line contains one integer T, indicating the number of test cases.\n\nEach of the following T lines describes a test case and contains only one integer n.\n\n1 ≤ T, n ≤ 60 000.\n\nFor each test case, output the answer modulo (109 + 7) in one line.\n\n## Input\n\nThe first line contains one integer T, indicating the number of test cases.Each of the following T lines describes a test case and contains only one integer n.1 ≤ T, n ≤ 60 000.\n\n## Output\n\nFor each test case, output the answer modulo (109 + 7) in one line.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of distinct variables.  \nLet $ \\mathcal{E}_n $ be the set of distinct algebraic expressions built from $ n $ distinct variables, using binary operations $ +, -, \\times, \\div $, and parentheses, such that:  \n- Each variable appears exactly once.  \n- Each operation is applied to two operands (variables or subexpressions).  \n- Two expressions are equivalent if they simplify to the same rational expression.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 60000 $  \n2. $ 1 \\leq n \\leq 60000 $  \n\n**Objective**  \nFor each test case with parameter $ n $, compute the number of non-equivalent algebraic expressions $ |\\mathcal{E}_n| \\mod (10^9 + 7) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10211L","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}