L. Lost In The Echo

Codeforces

IDCF10211L

Time8000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

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. He 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)? Two 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. The 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. For each test case, output the answer modulo (109 + 7) in one line. ## Input The 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. ## Output For each test case, output the answer modulo (109 + 7) in one line. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of distinct variables. Let $ \mathcal{E}_n $ be the set of distinct algebraic expressions built from $ n $ distinct variables, using binary operations $ +, -, \times, \div $, and parentheses, such that: - Each variable appears exactly once. - Each operation is applied to two operands (variables or subexpressions). - Two expressions are equivalent if they simplify to the same rational expression. **Constraints** 1. $ 1 \leq T \leq 60000 $ 2. $ 1 \leq n \leq 60000 $ **Objective** For each test case with parameter $ n $, compute the number of non-equivalent algebraic expressions $ |\mathcal{E}_n| \mod (10^9 + 7) $.

API Response (JSON)

{
  "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 influen...",
      "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...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments