{"problem":{"name":"D. Shake It!","description":{"content":"_A never-ending, fast-changing and dream-like world unfolds, as the secret door opens._ A world is an unordered graph _G_, in whose vertex set _V_(_G_) there are two special vertices _s_(_G_) and _t_","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF848D"},"statements":[{"statement_type":"Markdown","content":"_A never-ending, fast-changing and dream-like world unfolds, as the secret door opens._\n\nA world is an unordered graph _G_, in whose vertex set _V_(_G_) there are two special vertices _s_(_G_) and _t_(_G_). An initial world has vertex set {_s_(_G_), _t_(_G_)} and an edge between them.\n\nA total of _n_ changes took place in an initial world. In each change, a new vertex _w_ is added into _V_(_G_), **an existing edge** (_u_, _v_) is chosen, and two edges (_u_, _w_) and (_v_, _w_) are added into _E_(_G_). Note that it's possible that some edges are chosen in more than one change.\n\nIt's known that the capacity of the minimum _s_\\-_t_ cut of the resulting graph is _m_, that is, at least _m_ edges need to be removed in order to make _s_(_G_) and _t_(_G_) disconnected.\n\nCount the number of _non-similar worlds_ that can be built under the constraints, modulo 109 + 7. We define two worlds similar, if they are isomorphic and there is isomorphism in which the _s_ and _t_ vertices are not relabelled. Formally, two worlds _G_ and _H_ are considered similar, if there is a bijection between their vertex sets , such that:\n\n* _f_(_s_(_G_)) = _s_(_H_);\n* _f_(_t_(_G_)) = _t_(_H_);\n* Two vertices _u_ and _v_ of _G_ are adjacent in _G_ if and only if _f_(_u_) and _f_(_v_) are adjacent in _H_.\n\n## Input\n\nThe first and only line of input contains two space-separated integers _n_, _m_ (1 ≤ _n_, _m_ ≤ 50) — the number of operations performed and the minimum cut, respectively.\n\n## Output\n\nOutput one integer — the number of _non-similar worlds_ that can be built, modulo 109 + 7.\n\n[samples]\n\n## Note\n\nIn the first example, the following 6 worlds are pairwise non-similar and satisfy the constraints, with _s_(_G_) marked in green, _t_(_G_) marked in blue, and one of their minimum cuts in light blue.\n\nIn the second example, the following 3 worlds satisfy the constraints.\n\n","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"[{\"iden\":\"statement\",\"content\":\"_随着秘密之门的开启，一个永不停息、瞬息万变且如梦似幻的世界展开了。_\\n\\n一个 #cf_span(class=[tex-font-style-underline], body=[world]) 是一个无向图 #cf_span[G]，其顶点集 #cf_span[V(G)] 中包含两个特殊顶点 #cf_span[s(G)] 和 #cf_span[t(G)]。一个 #cf_span(class=[tex-font-style-underline], body=[initial world]) 的顶点集为 #cf_span[{s(G), t(G)}]，且其间有一条边相连。\\n\\n在某个 #cf_span(class=[tex-font-style-underline], body=[initial world]) 上，共发生了 #cf_span[n] 次变化。每次变化中，新增一个顶点 #cf_span[w]，并选择一条 #cf_span[已存在的边] #cf_span[(u, v)]，然后向 #cf_span[E(G)] 中添加两条边 #cf_span[(u, w)] 和 #cf_span[(v, w)]。注意，某些边可能在多次变化中被选中。\\n\\n已知所得图的最小 #cf_span[s]-#cf_span[t] 割的容量为 #cf_span[m]，即至少需要移除 #cf_span[m] 条边才能使 #cf_span[s(G)] 和 #cf_span[t(G)] 不连通。\\n\\n在给定约束下，计算可以构建的 _非相似世界_ 的数量，对 #cf_span[109 + 7] 取模。我们定义两个 #cf_span(class=[tex-font-style-underline], body=[worlds]) 是相似的，当且仅当它们同构，且存在一个同构映射使得 #cf_span[s] 和 #cf_span[t] 顶点未被重新标记。形式上，两个 #cf_span(class=[tex-font-style-underline], body=[worlds]) #cf_span[G] 和 #cf_span[H] 被认为是相似的，当且仅当存在它们顶点集之间的一个双射，满足：\\n\\n输入的第一行且仅有一行，包含两个用空格分隔的整数 #cf_span[n], #cf_span[m] (#cf_span[1 ≤ n, m ≤ 50]) —— 分别表示执行的操作次数和最小割的值。\"},{\"iden\":\"input\",\"content\":\"输入的第一行且仅有一行，包含两个用空格分隔的整数 #cf_span[n], #cf_span[m] (#cf_span[1 ≤ n, m ≤ 50]) —— 分别表示执行的操作次数和最小割的值。\"},{\"iden\":\"output\",\"content\":\"请输出一个整数——满足条件的 _非相似世界_ 的数量，对 #cf_span[109 + 7] 取模。\"},{\"iden\":\"examples\",\"content\":\"输入\\n3 2\\n输出\\n6\\n\\n输入\\n4 4\\n输出\\n3\\n\\n输入\\n7 3\\n输出\\n1196\\n\\n输入\\n31 8\\n输出\\n64921457\"},{\"iden\":\"note\",\"content\":\"在第一个例子中，以下 #cf_span[6] 个 #cf_span(class=[tex-font-style-underline], body=[worlds]) 两两不相似且满足约束条件，其中 #cf_span[s(G)] 标记为绿色，#cf_span[t(G)] 标记为蓝色，其中一个最小割标记为浅蓝色。 在第二个例子中，以下 #cf_span[3] 个 #cf_span(class=[tex-font-style-underline], body=[worlds]) 满足约束条件。 \"}]\n\n[{\"iden\":\"statement\",\"content\":\"_随着秘密之门的开启，一个永不停息、瞬息万变且如梦似幻的世界展开了。_\\n\\n一个 #cf_span(class=[tex-font-style-underline], body=[world]) 是一个无向图 #cf_span[G]，其顶点集 #cf_span[V(G)] 中包含两个特殊顶点 #cf_span[s(G)] 和 #cf_span[t(G)]。一个 #cf_span(class=[tex-font-style-underline], body=[initial world]) 的顶点集为 #cf_span[{s(G), t(G)}]，且其间有一条边相连。\\n\\n在某个 #cf_span(class=[tex-font-style-underline], body=[initial world]) 上，共发生了 #cf_span[n] 次变化。每次变化中，新增一个顶点 #cf_span[w]，并选择一条 #cf_span[已存在的边] #cf_span[(u, v)]，然后向 #cf_span[E(G)] 中添加两条边 #cf_span[(u, w)] 和 #cf_span[(v, w)]。注意，某些边可能在多次变化中被选中。\\n\\n已知所得图的最小 #cf_span[s]-#cf_span[t] 割的容量为 #cf_span[m]，即至少需要移除 #cf_span[m] 条边才能使 #cf_span[s(G)] 和 #cf_span[t(G)] 不连通。\\n\\n在给定约束下，计算可以构建的 _非相似世界_ 的数量，对 #cf_span[109 + 7] 取模。我们定义两个 #cf_span(class=[tex-font-style-underline], body=[worlds]) 是相似的，当且仅当它们同构，且存在一个同构映射使得 #cf_span[s] 和 #cf_span[t] 顶点未被重新标记。形式上，两个 #cf_span(class=[tex-font-style-underline], body=[worlds]) #cf_span[G] 和 #cf_span[H] 被认为是相似的，当且仅当存在它们顶点集之间的一个双射，满足：\\n\\n输入的第一行且仅有一行，包含两个用空格分隔的整数 #cf_span[n], #cf_span[m] (#cf_span[1 ≤ n, m ≤ 50]) —— 分别表示执行的操作次数和最小割的值。\"},{\"iden\":\"input\",\"content\":\"输入的第一行且仅有一行，包含两个用空格分隔的整数 #cf_span[n], #cf_span[m] (#cf_span[1 ≤ n, m ≤ 50]) —— 分别表示执行的操作次数和最小割的值。\"},{\"iden\":\"output\",\"content\":\"请输出一个整数——满足条件的 _非相似世界_ 的数量，对 #cf_span[109 + 7] 取模。\"},{\"iden\":\"examples\",\"content\":\"输入\\n3 2\\n输出\\n6\\n\\n输入\\n4 4\\n输出\\n3\\n\\n输入\\n7 3\\n输出\\n1196\\n\\n输入\\n31 8\\n输出\\n64921457\"},{\"iden\":\"note\",\"content\":\"在第一个例子中，以下 #cf_span[6] 个 #cf_span(class=[tex-font-style-underline], body=[worlds]) 两两不相似且满足约束条件，其中 #cf_span[s(G)] 标记为绿色，#cf_span[t(G)] 标记为蓝色，其中一个最小割标记为浅蓝色。 在第二个例子中，以下 #cf_span[3] 个 #cf_span(class=[tex-font-style-underline], body=[worlds]) 满足约束条件。 \"}]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions** \nLet $ G $ be an unordered graph with vertex set $ V(G) $ and edge set $ E(G) $, with two distinguished vertices $ s(G), t(G) \\in V(G) $. \nAn *initial world* is the graph with $ V(G) = \\{s, t\\} $ and $ E(G) = \\{(s, t)\\} $. \n\nA *world* is constructed by applying $ n $ operations: \n- In each operation, a new vertex $ w $ is added; \n- An existing edge $ (u, v) \\in E(G) $ is selected; \n- Two new edges $ (u, w) $ and $ (v, w) $ are added. \n\nLet $ \\mathcal{W}_{n,m} $ be the set of all non-similar worlds after $ n $ operations such that the minimum $ s $-$ t $ cut has capacity $ m $. \n\n**Constraints** \n1. $ 1 \\leq n, m \\leq 50 $ \n2. The graph is constructed from the initial world via exactly $ n $ operations as described. \n3. The minimum $ s $-$ t $ cut in the final graph has size exactly $ m $. \n\n**Objective** \nCount the number of non-similar worlds in $ \\mathcal{W}_{n,m} $, where two worlds $ G $ and $ H $ are *similar* if there exists a graph isomorphism $ \\phi: V(G) \\to V(H) $ such that $ \\phi(s(G)) = s(H) $ and $ \\phi(t(G)) = t(H) $. \n\nOutput the count modulo $ 10^9 + 7 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF848D","tags":["combinatorics","dp","flows","graphs"],"sample_group":[["3 2","6"],["4 4","3"],["7 3","1196"],["31 8","64921457"]],"created_at":"2026-03-03 11:00:39"}}