有 $n\,(2\le n\le 4\cdot 10^6)$ 个节点，编号 $1\sim n$，你一开始在节点 $n$，想要到节点 $1$。假设你现在在节点 $x$，你可以进行以下两种操作：

1. 选择一个正整数 $y\in \left[1, x - 1\right]$，并移动到节点 $x-y$。
2. 选择一个正整数 $z\in \left[2, x\right]$，并移动到节点 $\left\lfloor\frac{x}{z}\right\rfloor$。

求有多少种方案到达节点 $1$，只要有一次选择的 $x$ 或 $z$ 不同就算方案不同。答案对 $m$ 取模，其中 $m\in \left(10^8, 10^9\right)$ 且 $m$ 是素数。

构造一个 $n^3$ 个点的无向图 $G$，方法如下：

1. 给定 $3$ 张 $n$ 个点的无向图 $G_1,G_2,G_3$。
2. 构造 $n^3$ 个点，标号是一个三元组 $\left<i,j,k\right>$。
3. 对于 $G_1$ 中的边 $\left<u,v\right>$，连边 $\left<u,j,k\right>$ 和 $\left<v,j,k\right>$。
4. 对于 $G_2$ 中的边 $\left<u,v\right>$，连边 $\left<i,u,k\right>$ 和 $\left<i,v,k\right>$。
5. 对于 $G_3$ 中的边 $\left<u,v\right>$，连边 $\left<i,j,u\right>$ 和 $\left<i,j,v\right>$。
6. 对于 $G$ 上的一个点 $\left<i,j,k\right>$，其点权为 ${10}^{18(i+j+k)}$。

现在，要你求出 $G$ 的最大独立集大小膜 $998244353$ 以后的值。

$2\le n\le 10^5,1\le m_1,m_2,m_3\le 10^5$

给出一种生成长度为 $3n$ 的排列 $P$ 的方法：

1. 先生成一个长度为 $3n$ 的排列 $A$，然后对于 $\forall k\in [0,n-1]$，将 $3n + 1, 3n + 2, 3n + 3$ 分成一块。
2. 有 $n$ 个指针，开始指向这 $n$ 个块的开头。
3. 每次选择这 $n$ 个指针指向的数中最小的并将其放在 $P$ 的末尾，将这个指针向后移一位，如果移出块了，将指针删除。
4. 回到 2 操作直到所有指针均被删除。

现在要你求出，这样的方式共能生成多少种本质不同的排列 $A$，答案对 $m$ 取模。

$1\le n\le 2\times 10^3,10^8\le m\le 10^9+7$

有一个 $n\times n$ 的棋盘（$n\le 300$），然后对于每一列，考虑将所有该列纵坐标大于等于 $a_i$ 的格子全部删掉。在剩余期盼中，问有多少种放车的方案能使每个格子都能被至少一个车攻击到。

问存在多少个长度为 $n\,(2\le n\le 5000)$ 的单调不减序列 $a$，满足 $1\le a_i\le n$，且对于任意 $k\,(1\le k<n)$，都有：对任意大小为 $k$ 的子集 $S$ 和大小为 $k+1$ 的子集 $T$，满足 $\sum_{x\in S}A_x<\sum_{x\in T}A_x$。答案对大质数 $m$ 取模。

有一段标号从 $-\infty$ 到 $+\infty$ 的序列 $A$，初始是 $A_i=0$。现在有一个人在 $0$ 位置，有一段操作序列 $s$，依次进行操作。

假设 $i$ 时刻这个人在位置 $p$，如果 $s_i$ 是 '+'，则将 $A_p$ 加 $1$，如果是 '-'，则减 $1$；如果是 '<' 则该人左移一格，否则是 '>' 则右移一格。

要求数出 $s$ 的所有连续子串中最终得到的 $A$ 与 $s$ 最终得到相同 $A$ 序列的个数。

数据范围 $|s|\le 250000$。

有一张 $n$ 个点 $m$ 条边的简单无向图，每次选择一个度数小于等于 $1$ 的点然后将其删除，对于每个 $k$ 求删去 $k$ 个点的方案数。$n\le 100,\,m\le \frac{n\times(n-1)}{2}$。

有一个 $(n + 2) \times m$ 的长方形，除了第一行和最后一行，其他每一行每一天最左边和最右边的格子都有 $p$ 的概率被摧毁，每行之间独立且左边和右边独立，求 $k$ 天之后最上面一行与最下面一行四联通的概率。

其中 $1\le n,m\le 1500,\,0\le k\le 10^5$，答案对 $10^9+7$ 取模。

给定一个长度为$n$的字符串，其中只有 '(', ')', '?' 三种字符，其中 '?' 可以为 '(' 或者 ')'。对于一个括号序列，定义其权值为其通过删除字符后可以得到的合法的括号匹配的最深的深度，求出所有可能的括号序列（即问号替换后）的权值和。

在 D1 中，$n\le 2000$；在 D2 中，$n\le 10^6$。

题目大意就是有$n\,(n\le 30)$个点的无向完全图，有$m\,\left(m\le \frac{n\times (n-1)}{2}\right)$条道路上没有怪兽，其他道路都有怪兽。

一个人一开始在$1$号点，每次会随机选择一条路走并把这条路上的怪兽全部杀完。

问期望走多少步才能让这$n$个点之间都存在没有怪兽的路径。

按照国际惯例，多组数据，$T\le 100$。