← 返回题目列表

Codeforces · 848/D

D. 摇一摇!

中文机器翻译题面 查看原题

随着秘密之门的打开,一个永不停息、快速变化、梦幻般的世界展开。

世界是一个无序图 G,其顶点集 V(G) 中有两个特殊顶点 s(G) 和 t(G)。初始世界具有顶点集 {s(G), t(G)} 以及它们之间的边。

初始世界总共发生了n次变化。在每次更改中,一个新的顶点 w 被添加到 V(G) 中,选择一条现有边 (u, v),并将两条边 (u, w) 和 (v, w) 添加到 E(G) 中。请注意,某些边可能会在多次更改中被选择。

已知所得图的最小s-t割的容量为m,即至少需要删除m条边才能使s(G)和t(G)断开。

计算在约束下可以构建的非相似世界的数量,以 109 + 7 为模。我们定义两个相似的世界,如果它们同构并且存在同构,其中 s 和 t 顶点不被重新标记。形式上,如果两个世界 G 和 H 的顶点集 $$f 之间存在双射:V(G) \to V(H)$$,则认为它们是相似的,这样:

- f(s(G)) = s(H);
- f(t(G)) = t(H);
- G 的两个顶点 u 和 v 在 G 中相邻,当且仅当 f(u) 和 f(v) 在 H 中相邻。

输入

输入的第一行也是唯一一行包含两个空格分隔的整数 n, m (1 ≤ n, m ≤ 50) — 分别是执行的操作数和最小切割。

输出

输出一个整数——可以构建的非相似世界的数量,模 109 + 7。

示例

输入 #1

3 2

输出 #1

6

输入 #2

4 4

输出 #2

3

输入 #3

7 3

输出 #3

1196

输入#4

31 8

输出#4

64921457

注意

在第一个示例中,以下 6 个世界是成对非相似的并且满足约束,其中 s(G) 标记为绿色,t(G) 标记为蓝色,其中一个最小割为浅蓝色。

在第二个示例中,以下 3 个世界满足约束。