Hosting a contest is not easy. there are many difficulties such as producing English problem statements.
When hosting the qualification contest for acm class, the TAs, dR3@W0oN and K31iN encounter another problem. The qualification contest has two stages: In the first stage several students would qualify (and enter the next stage),
and in the second stage those qualified students would be divided into groups of three.
Because of the rule above, the TAs hope to select a problemset, such that the number of the students promoted from the first stage can be divided by 3. Also there must not be too little or too many participants that enter stage 2, so the problemset has to be selected so that at least L students, and at most U students can qualify.
The method of selection in stage one is:
a contestant is qualified if and only if he/she gets AC for at least 5 problems out of all 8 problems.
Now there are m (m<=20) problems in pool. And there are n (n<=500000) participants in stage one. The TAs will select 8 problems from the pool as the official contest problems in stage one. By careful analysis, dR3@W0oN and K31in are able to determine the capability of each participants: they know for each participants which problems they are able to solve.
Given the informations above (including L & U), calculate how many ways of problemset selection are there, so that the promotion result will be as required (i.e. divisible by 3, between L & U).
First line contains a number T, denoting the number of test cases.
Each test case starts with four integers n,m,L,U. Then follows n lines of string of length m. If i'th participant is able to solve j'th problem, the j'th character of i'th line is '1', and it's '0' otherwise.
T<=20
3<=n<=500000
8<=m<=20
3<=L<=U<=n
For each test case, please output one line indicating the answer for this test case.
2 3 12 3 3 100000001111 111111111111 111111111111 3 18 3 3 100000000000001111 111111111111111111 111111111111111111
35 286
Migrated from old NTUJ.
dreamoon
| No. | Testdata Range | Score |
|---|