{"problem":{"name":"F. Connecting Vertices","description":{"content":"There are _n_ points marked on the plane. The points are situated in such a way that they form a regular polygon (marked points are its vertices, and they are numbered in counter-clockwise order). You","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF888F"},"statements":[{"statement_type":"Markdown","content":"There are _n_ points marked on the plane. The points are situated in such a way that they form a regular polygon (marked points are its vertices, and they are numbered in counter-clockwise order). You can draw _n_ - 1 segments, each connecting any two marked points, in such a way that all points have to be connected with each other (directly or indirectly).\n\nBut there are some restrictions. Firstly, some pairs of points cannot be connected directly and have to be connected undirectly. Secondly, the segments you draw must not intersect in any point apart from the marked points (that is, if any two segments intersect and their intersection is not a marked point, then the picture you have drawn is invalid).\n\nHow many ways are there to connect all vertices with _n_ - 1 segments? Two ways are considered different iff there exist some pair of points such that a segment is drawn between them in the first way of connection, but it is not drawn between these points in the second one. Since the answer might be large, output it modulo 109 + 7.\n\n## Input\n\nThe first line contains one number _n_ (3 ≤ _n_ ≤ 500) — the number of marked points.\n\nThen _n_ lines follow, each containing _n_ elements. _a__i_, _j_ (_j_\\-th element of line _i_) is equal to 1 iff you can connect points _i_ and _j_ directly (otherwise _a__i_, _j_ = 0). It is guaranteed that for any pair of points _a__i_, _j_ = _a__j_, _i_, and for any point _a__i_, _i_ = 0.\n\n## Output\n\nPrint the number of ways to connect points modulo 109 + 7.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"平面上有 #cf_span[n] 个标记点，这些点构成一个正多边形（标记点为其顶点，按逆时针顺序编号）。你可以画出 #cf_span[n - 1] 条线段，每条线段连接任意两个标记点，使得所有点相互连通（直接或间接）。\n\n但存在一些限制：首先，某些点对不能直接连接，必须通过其他点间接连通；其次，你所画的线段除标记点外不能在任何其他点相交（即，若任意两条线段相交且交点不是标记点，则该图无效）。\n\n有多少种方式可以用 #cf_span[n - 1] 条线段连接所有顶点？两种方式不同，当且仅当存在某对点，在第一种方式中被线段直接连接，而在第二种方式中没有。由于答案可能很大，请输出对 #cf_span[109 + 7] 取模的结果。\n\n第一行包含一个数 #cf_span[n] (#cf_span[3 ≤ n ≤ 500]) —— 标记点的数量。\n\n接下来 #cf_span[n] 行，每行包含 #cf_span[n] 个元素。#cf_span[ai, j]（第 #cf_span[i] 行的第 #cf_span[j] 个元素）等于 #cf_span[1] 当且仅当你可以直接连接点 #cf_span[i] 和 #cf_span[j]（否则 #cf_span[ai, j = 0]）。保证对于任意两点对，#cf_span[ai, j = aj, i]，且对任意点 #cf_span[ai, i = 0]。\n\n请输出连接所有点的方式数，对 #cf_span[109 + 7] 取模。\n\n## Input\n\n第一行包含一个数 #cf_span[n] (#cf_span[3 ≤ n ≤ 500]) —— 标记点的数量。接下来 #cf_span[n] 行，每行包含 #cf_span[n] 个元素。#cf_span[ai, j]（第 #cf_span[i] 行的第 #cf_span[j] 个元素）等于 #cf_span[1] 当且仅当你可以直接连接点 #cf_span[i] 和 #cf_span[j]（否则 #cf_span[ai, j = 0]）。保证对于任意两点对，#cf_span[ai, j = aj, i]，且对任意点 #cf_span[ai, i = 0]。\n\n## Output\n\n请输出连接所有点的方式数，对 #cf_span[109 + 7] 取模。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ n \\geq 3 $ be an integer. Let $ P = \\{p_0, p_1, \\dots, p_{n-1}\\} $ be the vertices of a regular $ n $-gon, labeled in counter-clockwise order.\n\nLet $ A \\in \\{0,1\\}^{n \\times n} $ be a symmetric adjacency matrix with $ A_{i,i} = 0 $ for all $ i $, and $ A_{i,j} = A_{j,i} = 1 $ iff a direct segment may be drawn between $ p_i $ and $ p_j $.\n\nWe seek the number of non-crossing spanning trees on $ P $, using only edges $ (i,j) $ such that $ A_{i,j} = 1 $, where:\n\n- The tree has exactly $ n-1 $ edges.\n- The tree connects all $ n $ vertices.\n- No two edges intersect except possibly at endpoints (i.e., the drawing is planar and non-crossing).\n\nThe vertices lie in convex position (regular polygon), so a set of chords (edges) is non-crossing if and only if no two chords intersect in their interiors — which occurs iff the chords form a non-crossing partition.\n\nThus, the problem reduces to:\n\n> Count the number of non-crossing spanning trees on $ n $ labeled points in convex position, using only edges allowed by matrix $ A $.\n\nThis is equivalent to counting the number of non-crossing trees on a convex $ n $-gon with restricted edge set $ A $.\n\n---\n\n**Formal Statement:**\n\nLet $ \\mathcal{T}_n $ be the set of all non-crossing spanning trees on $ n $ labeled points in convex position (i.e., vertices of a regular $ n $-gon).\n\nGiven a symmetric binary adjacency matrix $ A \\in \\{0,1\\}^{n \\times n} $, define:\n\n$$\n\\mathcal{T}_A = \\left\\{ T \\in \\mathcal{T}_n \\,\\middle|\\, \\forall (i,j) \\in E(T),\\, A_{i,j} = 1 \\right\\}\n$$\n\nCompute:\n\n$$\n|\\mathcal{T}_A| \\mod (10^9 + 7)\n$$\n\n--- \n\n**Note:** The non-crossing condition on convex position implies that the tree must be a *non-crossing tree* — a tree whose edges are chords of the polygon that do not cross. This is a well-known structure in combinatorics, often approached via dynamic programming on intervals of the polygon.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF888F","tags":["dp","graphs"],"sample_group":[["3\n0 0 1\n0 0 1\n1 1 0","1"],["4\n0 1 1 1\n1 0 1 1\n1 1 0 1\n1 1 1 0","12"],["3\n0 0 0\n0 0 1\n0 1 0","0"]],"created_at":"2026-03-03 11:00:39"}}