4212: Fake bullions
内存限制：256 MB
时间限制：2 S
题面：传统
评测方式：文本比较
上传者：
提交：1
通过：1
题目描述
time limit per test
3 secondsmemory limit per test
512 megabytesinput
standard inputoutput
standard outputIn 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
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:
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.
Input
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
Print single integer: the number of different sets of b gangs the police can arrest modulo 109+7.Examples
Input
2 2 1
01
00
5 11000
6 100000
Output
2
Input
5 2 1
00000
10000
11011
11000
11010
2 00
1 1
6 100110
1 0
1 0
Output
5
输入样例 复制
输出样例 复制