有 $T$ 组数据，每组数据给出 $f, x, g, y, n, m$，你需要求出

$$\sum_{i = 0}^{n - 1} \left[ (fi + x) \bmod m < (gi + y) \bmod m \right]$$

数据范围：$1 \leq T \leq 10^4$，$1 \leq f, x, g, y, n, m \leq 10^6$。

时空限制：$1$s / $1024$MiB。

给出一棵包含 $n$ 个节点的树，边带权。

有 $Q$ 次询问，每次询问给出 $k$ 个区间 $[l_1, r_1], \cdots, [l_k, r_k]$，定义点集 $V$ 表示至少被一个区间包含的点构成的集合。

考虑 $V$ 的所有无序点对 $(u, v)$，将树上 $u, v$ 之间的简单路径上所有边进行染色。你需要求出所有被染色边的最大边权。

数据范围：$1 \leq n, Q\leq 2 \times 10^5$，$1 \leq \sum k \leq 2 \times 10^5$，$1 \leq l_i \leq r_i \leq n$。

时空限制：$2$s / $512$MiB。

已知三个整数 $a, b, c$。定义 $F_n(x) = (ax^2 + bx + c)^n$。

有 $Q$ 次询问，每次询问给出两个参数 $n, k$，你需要求出 $\sum_{i = 0}^k[x^i]F_n(x)$。答案对 $10^9 + 7$ 取模。

本题强制在线。

数据范围：$1 \leq a, b, c \leq 10^9 + 6$，$1 \leq Q \leq 3\times 10^5$，$0 \leq n \leq 3\times 10^5$，$0 \leq k \leq 2n$。

时空限制：$7$s / $1024$MiB。

对于一个多项式 $f(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n$，当 $a_i(0 \leq i \leq n)$ 均为非负整数且 $a_n \neq 0$ 时，多项式 $f(x)$ 被称为 $n$ 阶有效多项式。

对于一个 $n$ 阶有效多项式 $f(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n$，其孪生多项式 $g(x)$ 定义为

$$g(x) = \sum_{i = 0}^n i \cdot x^{a_i}$$

当且仅当 $f(x) = g(x)$ 时，$f(x)$ 被称为酷多项式。

给出一个不完整的 $n$ 阶有效多项式 $f(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n$，$a_i$ 的一部分已经确定，剩余部分暂未确定。保证 $a_0$ 与 $a_n$ 未确定。

请求出确定了未确定的部分以后，能得到多少个 $n$ 阶有效酷多项式。答案对 $10^9 + 7$ 取模。

数据范围：$1 \leq n \leq 4 \times 10^5$。

时空限制：$2$s / $256$MiB。

设 $v_p(x!)$ 表示 $x!$ 可以分解出多少个 $p$ 的乘积。

勒让德定理：

• 当 $p$ 为质数时

$$v_p(x!) = \sum_{j = 1}^{\lfloor \log_k x \rfloor} \left\lfloor \frac{x}{p^j} \right\rfloor$$

• 当 $p$ 为合数时，记 $p = \sum_{i = 1}^m p_i^{c_i}$

$$v_p(x!) = \min_{i = 1}^m \left\lfloor \frac{v_{p_i}(x!)}{c_i} \right\rfloor$$

设

$$w_k(a, b) = \begin{cases} \min(v_k(a!), v_k(b!)) & \text{if }v_k(a!) \neq v_k(b!) \text{;}\\ 10^{100} & \text{otherwise.} \end{cases}$$

设

$$f_m(a, b) = \min_{2 \leq k \leq m} w_k(a, b)$$

给出两个整数 $n, m$，你需要计算 $\sum\limits_{1 \leq x < n}f_m(x, n)$。

数据范围：$2 \leq n \leq m \leq 10^7$。可以证明给定条件下答案严格小于 $10^{100}$。

时空限制：$3$s / $512$MiB。

给出一个长度为 $n$ 的序列 $a_1, a_2, \cdots, a_n$，满足不存在 $1 \leq i < j < k < l \leq n$ 使得 $a_i \neq a_j$，$a_i = a_k$，$a_j = a_l$。

有 $Q$ 次询问，每次询问给出两个整数 $l, r(1 \leq l \leq r \leq n)$，你需要求出区间 $[l, r]$ 中所有出现了奇数次的数之和。

本题强制在线。

数据范围：$1 \leq n, Q \leq 5\times 10^5$，$1 \leq a_i \leq n$，$1 \leq l \leq r \leq n$。

时空限制：$10$s / $1024$MiB。

有一个 $n \times m$ 的网格图。最初，每个格点都没有颜色。

每次操作，你可以选择任意一行或一列染色。在第一次操作中，你只能选择颜色 $1$；在第 $i(i > 1)$ 次操作，你可以选择颜色 $c_{i - 1}$ 或 $c_{i - 1} + 1$（其中 $c_{i - 1}$ 表示第 $i - 1$ 次操作选择的颜色）。

如果满足以下条件，我们称最终的染色结果为优美：

• 每个单元格都被染色。
• $1 \sim k$ 的每个颜色都被使用（至少有一个单元格被染成该颜色）。

对于优美的最终染色，我们定义优美值为实现该染色方案最少需要的操作次数。

对于 $i = \min(n, m), \cdots, n + m - 1$，你需要求出优美值为 $i$ 的优美染色个数。

数据范围：$2 \leq n, m \leq 2000$，$1 \leq k \leq n + m - 1$。

时空限制：$3$s / $512$MiB。

给出一个关于 $n$ 的排列 $a$，对排列 $a$ 使用 Fast Bogosort：

• 如果数组已经有序，则算法终止。
• 否则，将数组划分成尽可能多的区间，每个区间 $[l, r]$ 恰好包含 $[l, r]$ 中的所有数字。注意区间不能重叠，并且他们的并集为 $[1, n]$。
• 对于每个被划分的区间 $[l, r]$，如果 $l < r$，则调用 shuffle(l, r)，在区间 $[l, r]$ 内均匀随机打乱数字。

现在，请你计算对排列 $a$ 使用 Fast Bogosort，shuffle 函数的期望调用次数。

数据范围：$1 \leq n \leq 10^5$。

时空限制：$3$s / $1024$MiB。

给出一个非负整数序列 $a_1, a_2, \cdots, a_n$。初始时，你可以创造一个机器人，高度为 $[0, d]$ 之间的正整数。每当经过一个检查点 $a_i$ 时，如果当前的高度 $h$ 满足 $h \geq a_i$，则高度 $h \gets h - a_i$；否则不会发生任何事。

有 $Q$ 次询问，每次询问给出两个正整数 $l, r(1 \leq l \leq r \leq n)$，你需要选择机器人的初始高度，使得依次经过检查点 $a_l, \cdots, a_r$ 之后机器人剩下的高度最大，你只需要求出该高度即可。

数据范围：$1 \leq n, Q \leq 3 \times 10^5$，$1 \leq d \leq 10^9$，$0 \leq a_i \leq 10^9$，$1 \leq l \leq r \leq n$。

时空限制：$1$s / $256$MiB。

有 $n$ 个人，分别位于坐标轴上的 $p_1, \cdots, p_n$ 位置。初始时 $p_i = i$。

你可以在坐标轴上的某个位置 $x(1 \leq x \leq n)$ 放置一个景点，接下来所有人都会朝着这个景点靠拢。具体地，对于每个人 $i$：

• 若 $p_i = x$，则位置不变。
• 若 $p_i < x$，则向右走一步 $p_i \gets p_i + 1$。
• 若 $p_i > x$，则向左走一步 $p_i \gets p_i - 1$。

每个位置 $x$ 都有一个对应的权值 $a_x$，对于某一时刻的站位数组 $p_1, \cdots, p_n$，得分定义为

$$\sum_{i = 1}^n a_{p_i}$$

你可以进行任意次操作，每次放置景点的位置任选。对于所有可能的站位数组 $p$，你需要求出得分总和。答案对 $998244353$ 取模。

数据范围：$1 \leq n \leq 2 \times 10^5$，$1 \leq a_i \leq 10^9$。

时空限制：$2$s / $256$MiB。