在伊萨特人们不会死。有n个犯罪团伙。第 i 个帮派包含 si 个恶人,从 0 到 si - 1 编号。其中一些人参与了一次大矿场抢劫,每人捡到了一根金条(这些人在输入中给出)。那发生在10100年前,然后所有的帮派都逃到了远离城镇的偏远地区。
这些年来,他们按照有组织的计划复制一些金条,以免被捕。他们构建了一个团体的锦标赛有向图(每对顶点之间恰好有一个有向边的图)(该图在输入中给出)。在此图中,从 u 到 v 的边意味着在第 i 小时内,u 团伙的 $$i \bmod s_{y}$$ 可以向 v 团伙的 $$i \bmod s_v$$ 发送假金条。如果他有一些金条(真金条或假金条),他就会发送假金条,而接收者没有任何金条。因此,在任何时刻,每个歹徒都拥有零个或一个金条。其中有些是真金条,有些是假金条。
今年年初,警方终于找到了该团伙,但和往常一样,他们没能抓到他们。警方决定开设一家珠宝店,让歹徒出售金条。因此,每个拥有金条(假的或真的)的歹徒都会试图出售它。如果他有真正的金条,他可以毫无问题地出售它,但如果他有假金条,则可能会发生以下两种事件:
- 此人成功出售金条。
- 此人被警方逮捕。
帮派的力量是指其中成功出售金条的人数。所有销售完成后,警方逮捕了顶级团伙中的b个团伙。按权力对帮派进行排序,我们将第一个帮派称为顶级帮派(您可以按每个顺序对相同权力进行排序)。考虑出售假金条的所有可能结果以及顶级帮派中B帮派的所有可能选择。计算这些 b 组的不同集合的数量,以 109 + 7 为模。如果某个组在 X 中但不在 Y 中,则两个集合 X 和 Y 被认为是不同的。
输入
第一行包含四个整数 n、a 和 b (1 ≤ b ≤ a ≤ n ≤ 5·103) — 帮派数量、语句中的常量 a 和 b。
接下来是n行,每行包含一个由0和1组成的大小为n的字符串。第 i 行中的第 j 个字符等于 1,则顶点 i 具有到顶点 j 的有向边。如果 i ≠ j,则保证 aii = 0 且 aij + aji = 1。
接下来是 n 行,每行以整数 si (1 ≤ si ≤ 2·106) ——第 i 个帮派中的匪徒数量开始,然后包含一串由 0 和 1 组成的长度为 si 的字符串。如果第i个帮派的第j个人最初有真金条,则第j个字符为0,否则为1。保证si之和不超过2·106。
输出
打印单个整数:警方可以逮捕的不同组b团伙的数量以109 + 7为模。
示例
输入 #1
2 2 1 01 00 5 11000 6 100000
输出 #1
2
输入 #2
5 2 1 00000 10000 11011 11000 11010 2 00 1 1 6 100110 1 0 1 0
输出 #2
5