{"problem":{"name":"F. Fake bullions","description":{"content":"In Isart people don't die. There are _n_ gangs of criminals. The _i_\\-th gang contains _s__i_ evil people numerated from 0 to _s__i_ - 1. Some of these people took part in a big mine robbery and picke","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF804F"},"statements":[{"statement_type":"Markdown","content":"In Isart people don't die. There are _n_ gangs of criminals. The _i_\\-th gang contains _s__i_ evil people numerated from 0 to _s__i_ - 1. Some of these people took part in a big mine robbery and picked **one** gold bullion each (these people are given in the input). That happened 10100 years ago and then all of the gangs escaped to a remote area, far from towns.\n\nDuring the years, they were copying some gold bullions according to an organized plan in order to not get arrested. They constructed a **tournament** directed graph (a graph where there is exactly one directed edge between every pair of vertices) of gangs (the graph is given in the input). In this graph an edge from _u_ to _v_ means that in the _i_\\-th hour the person of the gang _u_ can send a fake gold bullion to person of gang _v_. He sends it if he has some bullion (real or fake), while the receiver doesn't have any. Thus, at any moment each of the gangsters has zero or one gold bullion. Some of them have real bullions, and some of them have fake ones.\n\nIn the beginning of this year, the police has finally found the gangs, but they couldn't catch them, as usual. The police decided to open a jewelry store so that the gangsters would sell the bullions. Thus, every gangster that has a bullion (fake or real) will try to sell it. If he has a real gold bullion, he sells it without problems, but if he has a fake one, there is a choice of two events that can happen:\n\n*   The person sells the gold bullion successfully.\n*   The person is arrested by police.\n\nThe power of a gang is the number of people in it that successfully sold their bullion. After all selling is done, the police arrests _b_ gangs out of _top_ gangs. Sort the gangs by powers, we call the first _a_ gang _top_ gangs(you can sort the equal powers in each order). Consider all possible results of selling fake gold bullions and all possible choice of _b_ gangs among the _top_ gangs. Count the number of different sets of these _b_ gangs modulo 109 + 7. Two sets _X_ and _Y_ are considered different if some gang is in _X_ and isn't in _Y_.\n\n## Input\n\nThe first line contains four integers _n_, _a_ and _b_ (1 ≤ _b_ ≤ _a_ ≤ _n_ ≤ 5·103) — the number of gangs, the constants _a_ and _b_ from the statement.\n\nThen _n_ lines follow, each line contains a string of size _n_ consisting of zeros and ones. The _j_\\-th character in the _i_\\-th of these lines is equal to 1, then the vertex _i_ have a directed edge to the vertex _j_. It is guaranteed that _a__ii_ = 0 and _a__ij_ + _a__ji_ = 1 if _i_ ≠ _j_.\n\nThen _n_ lines follow, each line starts with the integer _s__i_ (1 ≤ _s__i_ ≤ 2·106) — the number of gangsters in the _i_\\-th gang, and then contains a string of zeros and ones with length _s__i_. The _j_\\-th character is 0 if the _j_\\-th person of the _i_\\-th gang had a real gold bullion initially, otherwise it is 1. It is guaranteed that the sum of _s__i_ does not exceed 2·106.\n\n## Output\n\nPrint single integer: the number of different sets of _b_ gangs the police can arrest modulo 109 + 7.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"在 Isart，人们不会死亡。这里有 #cf_span[n] 个犯罪团伙。第 #cf_span[i] 个团伙包含 #cf_span[si] 个邪恶的人，编号从 #cf_span[0] 到 #cf_span[si - 1]。其中一些人参与了一次大规模的矿井抢劫，每人捡到了 *一枚* 金条（这些人的信息在输入中给出）。这件事发生在 #cf_span[10100] 年前，之后所有团伙逃到了远离城镇的偏远地区。\n\n这些年来，他们按照一个有组织的计划复制了一些金条，以避免被捕。他们构建了一个团伙之间的 *锦标赛* 有向图（图中每对顶点之间恰好有一条有向边），该图在输入中给出。图中从 #cf_span[u] 到 #cf_span[v] 的边表示在第 #cf_span[i] 小时，团伙 #cf_span[u] 的人可以向团伙 #cf_span[v] 的人发送一枚假金条，前提是发送者拥有一枚金条（真或假），而接收者没有。因此，在任何时刻，每个匪徒至多拥有一枚金条。其中一些人拥有真金条，另一些人拥有假金条。\n\n今年年初，警方终于找到了这些团伙，但像往常一样没能抓到他们。警方决定开一家珠宝店，以便匪徒们出售金条。因此，每个拥有金条（真或假）的匪徒都会尝试出售它。如果他拥有真金条，则能顺利售出；但如果他拥有假金条，则可能发生以下两种情况之一：\n\n一个团伙的势力是成功售出其金条的人数。所有出售完成后，警方将逮捕 _前_ #cf_span[a] 个团伙中的 #cf_span[b] 个团伙。将团伙按势力排序，我们将前 #cf_span[a] 个团伙称为 _前_ 团伙（势力相等的团伙可以任意排序）。考虑所有可能的假金条出售结果以及所有可能从 _前_ 团伙中选择 #cf_span[b] 个团伙的方式，计算不同的 #cf_span[b] 个团伙集合的数量，结果对 #cf_span[109 + 7] 取模。两个集合 #cf_span[X] 和 #cf_span[Y] 被认为不同，当且仅当存在某个团伙在 #cf_span[X] 中但不在 #cf_span[Y] 中。\n\n第一行包含四个整数 #cf_span[n], #cf_span[a] 和 #cf_span[b]（#cf_span[1 ≤ b ≤ a ≤ n ≤ 5·103]）— 团伙数量，以及题目中的常数 #cf_span[a] 和 #cf_span[b]。\n\n接下来 #cf_span[n] 行，每行包含一个长度为 #cf_span[n] 的由 0 和 1 组成的字符串。第 #cf_span[i] 行的第 #cf_span[j] 个字符为 #cf_span[1] 表示从顶点 #cf_span[i] 到顶点 #cf_span[j] 存在一条有向边。保证 #cf_span[aii = 0] 且当 #cf_span[i ≠ j] 时 #cf_span[aij + aji = 1]。\n\n接着 #cf_span[n] 行，每行以整数 #cf_span[si]（#cf_span[1 ≤ si ≤ 2·106]）开头，表示第 #cf_span[i] 个团伙中匪徒的数量，然后是一个长度为 #cf_span[si] 的由 0 和 1 组成的字符串。第 #cf_span[j] 个字符为 #cf_span[0] 表示第 #cf_span[i] 个团伙的第 #cf_span[j] 个匪徒最初拥有真金条，否则为 #cf_span[1]。保证所有 #cf_span[si] 的总和不超过 #cf_span[2·106]。\n\n输出一个整数：警方可能逮捕的 #cf_span[b] 个团伙的不同集合数量，对 #cf_span[109 + 7] 取模。\n\n## Input\n\n第一行包含四个整数 #cf_span[n], #cf_span[a] 和 #cf_span[b]（#cf_span[1 ≤ b ≤ a ≤ n ≤ 5·103]）— 团伙数量，以及题目中的常数 #cf_span[a] 和 #cf_span[b]。接下来 #cf_span[n] 行，每行包含一个长度为 #cf_span[n] 的由 0 和 1 组成的字符串。第 #cf_span[i] 行的第 #cf_span[j] 个字符为 #cf_span[1] 表示从顶点 #cf_span[i] 到顶点 #cf_span[j] 存在一条有向边。保证 #cf_span[aii = 0] 且当 #cf_span[i ≠ j] 时 #cf_span[aij + aji = 1]。接下来 #cf_span[n] 行，每行以整数 #cf_span[si]（#cf_span[1 ≤ si ≤ 2·106]）开头，表示第 #cf_span[i] 个团伙中匪徒的数量，然后是一个长度为 #cf_span[si] 的由 0 和 1 组成的字符串。第 #cf_span[j] 个字符为 #cf_span[0] 表示第 #cf_span[i] 个团伙的第 #cf_span[j] 个匪徒最初拥有真金条，否则为 #cf_span[1]。保证所有 #cf_span[si] 的总和不超过 #cf_span[2·106]。\n\n## Output\n\n输出一个整数：警方可能逮捕的 #cf_span[b] 个团伙的不同集合数量，对 #cf_span[109 + 7] 取模。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, a, b \\in \\mathbb{Z} $ with $ 1 \\leq b \\leq a \\leq n \\leq 5000 $.  \nLet $ G = (V, E) $ be a tournament digraph on $ n $ vertices (gangs), where $ V = \\{0, 1, \\dots, n-1\\} $, and for all $ i \\ne j $, exactly one of $ (i,j) \\in E $ or $ (j,i) \\in E $ holds, with $ (i,i) \\notin E $.  \nFor each gang $ i \\in V $, let $ s_i \\in \\mathbb{Z}^+ $ be the number of gangsters, and let $ B_i \\in \\{0,1\\}^{s_i} $ be the initial bullion type vector: $ B_i[j] = 0 $ if the $ j $-th gangster has a **real** bullion, $ B_i[j] = 1 $ if **fake**.\n\n**Constraints**  \n1. The total sum $ \\sum_{i=0}^{n-1} s_i \\leq 2 \\cdot 10^6 $.  \n2. The tournament $ G $ is complete and asymmetric: $ \\forall i \\ne j, \\, A_{i,j} + A_{j,i} = 1 $, $ A_{i,i} = 0 $.  \n\n**Transmission Rule**  \nAt each hour, for each directed edge $ (u,v) \\in E $, if gangster $ x \\in \\text{gang}_u $ has **at least one** bullion (real or fake) and gangster $ y \\in \\text{gang}_v $ has **none**, then $ x $ may send **one** bullion to $ y $.  \nAll such transmissions occur in parallel over time, and the process continues until no more transmissions are possible.  \nEach gangster ends with **at most one** bullion.\n\n**Fake Bullion Behavior**  \nA gangster with a **fake** bullion may either:  \n- Keep it (and fail to sell), or  \n- Successfully sell it (counted as a sale).  \nEach fake bullion independently chooses one of these two outcomes.\n\n**Power of a Gang**  \nThe power $ p_i $ of gang $ i $ is the number of its gangsters who **successfully sold** a bullion (real or fake).  \n- Real bullions are always sold.  \n- Fake bullions are sold with binary choice (each independently).\n\n**Top Gangs**  \nSort gangs by descending power $ p_i $. Let the top $ a $ gangs be the first $ a $ in this ordering (ties broken arbitrarily).  \nLet $ \\mathcal{S} $ be the set of all possible outcomes of fake bullion sales (i.e., all assignments of sell/don’t-sell to fake bullions).  \nFor each outcome $ \\sigma \\in \\mathcal{S} $, let $ P_\\sigma = (p_0^\\sigma, \\dots, p_{n-1}^\\sigma) $ be the resulting power vector.  \nLet $ T_\\sigma \\subseteq V $ be the set of top $ a $ gangs under $ P_\\sigma $ (any tie-breaking allowed).  \nLet $ \\mathcal{F} $ be the family of all possible subsets of $ b $ gangs that can be selected from some $ T_\\sigma $, over all $ \\sigma \\in \\mathcal{S} $.\n\n**Objective**  \nCompute $ |\\mathcal{F}| \\mod (10^9 + 7) $, the number of distinct $ b $-element subsets of gangs that can appear as a subset of the top $ a $ gangs under some outcome of fake bullion sales.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF804F","tags":["combinatorics","dfs and similar","dp","graphs","number theory"],"sample_group":[["2 2 1\n01\n00\n5 11000\n6 100000","2"],["5 2 1\n00000\n10000\n11011\n11000\n11010\n2 00\n1 1\n6 100110\n1 0\n1 0","5"]],"created_at":"2026-03-03 11:00:39"}}