Fake bullions
Contest: Codeforces Round 411 (Div. 1)
Difficulty rating: 3400
Tags: combinatorics, dfs and similar, dp, graphs, number theory

In Isart people don't die. There are n gangs of criminals. The i-th gang contains si evil people numerated from 0 to si - 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 $$i \bmod s_{y}$$ of the gang u can send a fake gold bullion to person $$i \bmod s_v$$ 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.

Input format:
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 aii = 0 and aij + aji = 1 if i ≠ j.

Then n lines follow, each line starts with the integer si (1 ≤ si ≤ 2·106) — the number of gangsters in the i-th gang, and then contains a string of zeros and ones with length si. 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 si does not exceed 2·106.

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

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Example input:
2 2 1
01
00
5 11000
6 100000

Example output:
2

Example input:
5 2 1
00000
10000
11011
11000
11010
2 00
1 1
6 100110
1 0
1 0

Example output:
5

Editorial:
As the hints said this problem have two part:
First we want to solve the first part that is evaluating the mni and mxi for gangs. Obviously mni will be the number of thieves have a gold in i-th gang.
lemma1:Consider there is just a single edge from v to u; as hints said if one thief in v with index i has a gold it copied its gold to every j in u if and only if $$i \mod gcd(s_v, s_u) = j \mod gcd(s_v, s_u)$$ .
Now we call f(v, g) that g|szv as a gang with size g that thief number i has a gold in this gang if and only if one of the thiefs with index j in v-th gang has a gold such that $$j \mod g = i$$.
lemma2: Consider two edge like $$\tilde{u}\sim u$$ and $$u \sim w$$. as thing said in hints and above we can consider that v affect in w like this edge:
$$f(v,\gcd(sz_v,sz_u))\sim w$$.
lemma3: Consider a directed walk like w1, w2, , ..., wn. from two last lemmas we can consider the affect of w1 on wn as:
lemma4: Consider a closed directed walk from v like v,  w1,  w2,  ...,  wn,  v from three last lemmas we can consider $$m x _ { v } = m x _ { u } \cdot \frac { s _ { v } } { s _ { u } }$$ in which u is f(v, gcd(v, w1, w2, ..., wn)).
So now decompose graph of gangs to maximal strongly connected components from lemma4 for every component like a1, a2, ..., an, we can consider in place of all of them gang v with size equal to g = gcd(a1, a2, ..., an) such that i-th thief has a gold in v if and only if there is a j such that i-th thief in f(aj, g) has a gold.
So we decreased the problem to a dag tournament, Let's sort the vertices with topological sort. We'll find a Hamiltonian path of vertices such that for every different i and j there is directed edge from i-th vertex of the path to j-th vertex of the path if and only if i < j. By the lemma 2 it's sufficient to solve the problem for the path itself. So we decreased the problem to a only path. For the path, just do greedily, for each i from 1 to n affect the i-th vertex on the i + 1-th vertex, it can be done with complexity $${\mathcal {O}}\left(\sum _{i=1}^{n}s_{i}\right)$$. So mxi is equal to the number of ones after doing all of the things.
For every vertex we'll consider a mxi and mni.We sort this scores in an array T. |T| = 2·n.
Starting from biggest to smallest one. When we reach maximum of i-th vertex and, we fix this vertex and count number of sets he is in which and it has the minimum score of the set:
There is two kinds of vertices, q element of array mn are more than or equal to mni, and of the others, p elements of array mx are more than mxi(means if j-th vertex is in the second kind then mni ≤ mxi < mxj.
So we have to fix number of second kind of vertices as j(1 ≤ j ≤ min(b - 1, p)) and for all j do this: $$\text{If } (q+j < a) \text{ then } ans = ans + {p \choose j} \cdot {q \choose B-1-j}$$
It is clear when we fix maximum of j-th and i-th vertex as the minimum score of the set, we didn’t count one such sets twice and when fixing i-th vertex the fact holds. Also it is clear we count all of the situations. The complexity of this part is $${ \mathcal { O } } ( n \cdot b )$$.