在无向连通图中，若一条边被删除后，图会分成不连通的两部分，则称该边为割边。

求满足如下条件的无向连通图的数量：

1. 由 $n$ 个结点构成，结点有标号。
2. 割边不超过 $m$ 条。
3. 没有重边和自环。

答案对 $10^{9}+7$ 取模。

$2≤n≤50,0≤m≤\dfrac{n(n-1)}{2}$

一天，他问了小 H 和小 W 这样一个问题：

如果在一个圆上有 $n$ 个不同的点，依次标号为 $1$ 到 $n$，有多少种方案能把它们连成一棵树？

小 H & 小 W：这不是sb题吗？

小 L：那如果连边不能相交呢？

小 H & 小 W：这不是sb题吗？

小 L：那如果把「树」换成「图」呢呢？

小 H & 小 W：这不是sb题吗？

小 L：那如果给每个点一个权值 $a_i$，连接 $(i,j)$ 的边权值为 $a_i\times a_j$，求满足上面的图的期望所有边权值之和呢？

小 H & 小 W：这不是sb题吗？

小 L 见自己辛苦做了许久都没写出的题目被 dalao 轻松秒杀后十分郁闷。为了安慰他，你需要帮他做出这个问题。

注意

1. 两条边在端点处不视作相交。
2. 没有边的图（即只有 $n$ 个点，之间没有边相连）也合法
3. 点按顺时针从 $1$ 到 $n$ 编号。
4. 图中不能有自环和重边

这个背包最多可以装 $10^5$ 大小的东西

付公主有 $n$ 种商品，她要准备出摊了

每种商品体积为 $v_i$，都有无限件

给定 $m$，对于 $s\in [1,m]$，请你回答用这些商品恰好装 $s$ 体积的方案数。

小C有一个集合 $S$，里面的元素都是小于 $m$ 的非负整数。他用程序编写了一个数列生成器，可以生成一个长度为 $n$ 的数列，数列中的每个数都属于集合 $S$。

小C用这个生成器生成了许多这样的数列。但是小C有一个问题需要你的帮助：给定整数 $x$，求所有可以生成出的，且满足数列中所有数的乘积 $\bmod \ m$ 的值等于 $x$ 的不同的数列的有多少个。

小C认为，两个数列 $A$ 和 $B$ 不同，当且仅当 $\exists i \text{ s.t. } A_i \neq B_i$。另外，小C认为这个问题的答案可能很大，因此他只需要你帮助他求出答案对 $1004535809$ 取模的值就可以了。

黑板上有一个整数 $x$，初始时它的值为 $[0,n]$ 中的某一个整数，其中为 $i$ 的概率是 $p_i$

每一轮你可以将 $x$ 完全随机地替换成 $[0,x]$ 中的一个数。

求 $m$ 轮后，对于每个 $i\in[0,n]$，$x=i$ 的概率。

$n \le 10^5$，$m \le 10^{18}$，答案对 $998244353$ 取模。

生成测试数据并非简单的任务！生成大的随机数据通常不能够完全保证解法的正确性。

举个例子，考虑以前 Codeforces round 的一道题。它的输入格式如下：

第一行是一个整数 $n(1\leq n \leq max_n)$ 表示集合的大小，第二行包含 $n$ 个互不相同的整数 $a_1,a_2,\dots,a_n(1\leq a_i\leq max_a)$ 表示集合中的元素，升序排列。

如果你不注意题目的解法，看起来生成一个好的测试数据是非常容易的。令 $n=max_n$，从 $1\sim max_a$ 中生成 $n$ 个不相同的数，并排序。但是马上你就会知道这不那么简单。

下面是这道题目的真实解法。令 $g$ 为 $a_1,a_2,\dots,a_n$ 的最大公约数，令 $x=a_n/g-n$，如果 $x$ 是奇数输出 Alice，如果 $x$ 是偶数输出 Bob

考虑这道题两个错误的解法，它们与正解只在计算 $x$ 中不同。

第一个解法令 $x = a_n/g$ （不减去 $n$）

第二个解法令 $x=a_n-n$（不除以 $g$）

如果一个测试数据令这两个解法都输出错误的答案，称这个数据是有趣的。

给定 $max_n, max_a, q$ 求满足限制且有趣的测试数据的数量对 $q$ 取模的结果。

$1\leq max_n\leq 30000, max_n\leq max_a\leq 10^9, 10^4\leq q\leq 10^5+129$

有一排 $n$ 个球，定义一个组可以只包含一个球或者包含两个相邻的球。现在一个球只能分到一个组中，求从这些球中取出 $k$ 组的方案数。

$n\le 10^9$，$k<2^{15}$。

对于一个整数序列 $\{a_1, a_2, \ldots, a_n\}$，我们定义它的变换为 $\{b_1, b_2, \ldots, b_n\}$，其中 $b_i = a_1 | a_2 | \ldots | a_i$，其中 $|$ 表示二进制按位或运算。

现在求有多少个长为 $n$ 的序列 $a$，满足 $1\leq a_i \leq 2^k - 1$，使得它的变换 $b$ 是严格单调递增的，对 $10^9+7$ 取模。

$1\leq n \leq 10^{18}$，$1\leq k \leq 3 \times 10^4$。

给定一张 $n$ 个点 $m$ 条边的无重边无自环的有向图，你要从 $1$ 号点到 $n$ 号点去。

如果你在 $t$ 时刻之后到达 $n$ 号点，你要交 $x$ 元的罚款。

每条边从 $a_i$ 到 $b_i$，走过它需要花费 $c_i$ 元，多次走过同一条边需要多次花费。

走过每条边所需的时间是随机的，对于 $k \in [1,t]$，$\frac{p_{i,k}}{10^5}$ 表示走过第 $i$ 条边需要时间 $k$ 的概率。因此如果多次走过同一条边，所需的时间也可能不同。

你希望花费尽可能少的钱（花费与罚款之和）到达 $n$ 号点，因此每到达一个点，你可能会更改原有的计划。

求在最优决策下，你期望花费的钱数。

$n \le 50$，$m \le 100$，$t \le 2 \times 10^4$，$x,c_i \le 10^6$，$\sum_{k=1}^t p_{i,k} = 10^5$，答案精度误差 $\le 10^{-6}$。

给出一个门限值 $k$ 和两个只包含 $\texttt{AGCT}$ 四种字符的基因串 $S$ 和 $T$。现在你要找出在下列规则中 $T$ 在 $S$ 中出现了几次。

$T$ 在 $S$ 的第 $i$ 个位置中出现，当且仅当把 $T$ 的首字符和 $S$ 的第 $i$ 个字符对齐后，$T$ 中的每一个字符能够在 $S$ 中找到一个位置偏差不超过 $k$ 的相同字符。

即对于所有的 $j \in[1,|T|]$，都存在一个 $p \in [1,|S|]$ 使得 $|(i+j-1)-p| \leq k$ 且 $S_p=T_j$ 。

例如 $k=1$ 时，$\texttt{ACAT}$ 出现在 $\texttt{AGCAATTCAT}$ 的 $2$ 号， $3$ 号和 $6$ 号位置。 (编号从 $1$ 开始。)