CF804F.Fake bullions

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.

During 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.

In 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:

• The person sells the gold bullion successfully.
• The person is arrested by police.

The 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 $ 个犯罪团伙。第 $ i $ 个团伙包含 $ s_i $ 个邪恶之人，编号从 $ 0 $ 到 $ s_i - 1 $。其中一些人曾参与一场大规模矿场抢劫，并各自拿走了一块金锭（这些人在输入中给出）。此事发生在 $ 10^{100} $ 年前，此后所有团伙逃往远离城镇的偏远地区。

多年来，他们依据一项周密计划复制金锭，以避免被捕。他们构建了一个团伙之间的有向锦标赛图（即：任意两个顶点之间恰有一条有向边）——该图在输入中给出。在此图中，从 $ u $ 指向 $ v $ 的一条边表示：在第 $ i $ 小时，团伙 $ u $ 中编号为

的人可向团伙 $ v $ 中编号为

的人发送一枚伪造金锭。发送条件是：发送者当前持有至少一枚金锭（真实或伪造），而接收者尚未持有任何金锭。因此，在任意时刻，每个罪犯手中持有的金锭数量为 $ 0 $ 或 $ 1 $。其中部分人持有真实金锭，另一些人持有伪造金锭。

今年年初，警方终于找到了这些团伙，但一如往常，未能将其抓获。警方决定开设一家珠宝店，诱使罪犯前来出售金锭。于是，所有持有金锭（无论真假）的罪犯都会尝试出售。若持有真实金锭，则可顺利售出；若持有伪造金锭，则可能发生以下两种情形之一：

• 该人成功售出金锭；
• 该人被警方逮捕。

一个团伙的“势力”定义为该团伙中成功售出金锭的人数。全部销售结束后，警方将从“顶尖团伙”中逮捕 $ b $ 个团伙。我们将所有团伙按其势力由大到小排序（势力相等时顺序任意），称排名前 $ a $ 的团伙为“顶尖团伙”。考虑所有可能的伪造金锭销售结果，以及所有从顶尖团伙中选出 $ b $ 个团伙的方式，求这些 $ b $ 个团伙所构成的不同集合的总数（对 $ 10^9 + 7 $ 取模）。若集合 $ X $ 与 $ Y $ 中存在某个团伙属于 $ X $ 而不属于 $ Y $，则认为二者不同。

The 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.

Then 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.

Then 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$、$a$ 和 $b$（$1 ≤ b ≤ a ≤ n ≤ 5·10^3$）—— 分别表示帮派的数量，以及题目描述中的常数 $a$ 和 $b$。

接下来是 $n$ 行，每行包含一个长度为 $n$ 的由 0 和 1 组成的字符串。在这些行中，第 $i$ 行的第 $j$ 个字符若为 1，则表示顶点 $i$ 到顶点 $j$ 存在一条有向边。保证对所有 $i$ 有 $a_{ii} = 0$，且当 $i \ne j$ 时，$a_{ij} + a_{ji} = 1$。

随后是 $n$ 行，每行以整数 $s_i$（$1 ≤ s_i ≤ 2·10^6$）开头——表示第 $i$ 个帮派中帮派成员的数量；之后是一个长度为 $s_i$ 的由 0 和 1 组成的字符串。其中第 $j$ 个字符为 0 表示第 $i$ 个帮派的第 $j$ 名成员最初持有真金金锭，否则（即为 1）表示持有假金金锭。保证所有 $s_i$ 的总和不超过 $2·10^6$。

Print single integer: the number of different sets of b gangs the police can arrest modulo 109 + 7.

输出一个整数：警察可以逮捕的由 $b$ 个帮派组成的不同的集合的数量，对 $10^9 + 7$ 取模。