「FAOI-R3」移民计划

Luogu

IDLGP10154

Time2000ms

Memory512MB

DifficultyP4

数学O2优化

给定两个正整数 $n,a$。现有两个正整数数列 $\{h_n\},\{s_n\}$ 和一个正整数 $W$，满足： $$\begin{cases} s_1=a, \\ s_i=\left\lceil \dfrac{h_{i-1}}{i} \right\rceil, \\ h_i=i \times s_i,\\ W=h_1\times h_2\times \ldots\times h_n. \end{cases}$$ 试计算 $W$ 的值。**答案对 $10^9+7$ 取模。** ## Input **本题有多组数据。** 第一行，一个正整数 $T$，表示数据组数。下面 $T$ 行，每行两个整数 $n,a$。 ## Output $T$ 行，每行一个整数，对应一组数据的答案。 [samples] ## Note 样例解释： - 对于第 $1$ 组数据，$s$ 数列为 $\{1\}$，$h$ 数列为 $\{1\}$，故答案为 $1$。 - 对于第 $2$ 组数据，$s$ 数列为 $\{4,2\}$，$h$ 数列为 $\{4,4\}$，故答案为 $16$。 - 对于第 $3$ 组数据，$s$ 数列为 $\{9,5,4\}$，$h$ 数列为 $\{9,10,12\}$，故答案为 $1080$。 - 对于第 $4$ 组数据，取模前的答案为 $16721510400$。 ------------ | 测试点编号 | $n \le$ | $a \le$ | 分值 | | :----------: | :----------: | :----------: | :----------: | | $1$ | $100$ | $1000$ | $40$ | | $2$ | $10^7$ | $1000$ | $30$ | | $3$ | $10^7$ | $10^6$ | $30$ | 对于 $100\%$ 的数据，$1 \le T \le 10^5$，$1 \le n \le 10^7$，$1 \le a \le 10^6$。

Samples

Input #1

7
1 1
2 4
3 9
10 6
23 44
108 301
9181918 918918

Output #1

API Response (JSON)

{
  "problem": {
    "name": "「FAOI-R3」移民计划",
    "description": {
      "content": "给定两个正整数 $n,a$。 现有两个正整数数列 $\\{h_n\\},\\{s_n\\}$ 和一个正整数 $W$，满足： $$\\begin{cases} s_1=a, \\\\  s_i=\\left\\lceil \\dfrac{h_{i-1}}{i} \\right\\rceil, \\\\  h_i=i \\times s_i,\\\\  W=h_1\\times h_2\\times \\ldots\\times h_n.",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10154"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定两个正整数 $n,a$。\n\n现有两个正整数数列 $\\{h_n\\},\\{s_n\\}$ 和一个正整数 $W$，满足：\n\n$$\\begin{cases} s_1=a, \\\\  s_i=\\left\\lceil \\dfrac{h_{i-1}}{i} \\right\\rceil, \\\\  h_i=i \\times s_i,\\\\  W=h_1\\times h_2\\times \\ldots\\times h_n....",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments