Whole submatrix

Problem code: WINDOW2

All submissions for this problem are available.

After Chef successfully built a modern (L, K)-window on the attic wall he decided to expand the notion of the (L, K)-window in some other areas. Now he considers a rectangular grid that contains only zeroes and ones and has size N x M. He considers the (L, K)-window here as any submatrix of size L x K that contains only ones. Formally he defines (L, K)-window as any (K+L)-tuple (R1, ..., RL, C1, ..., CK) such that 1 <= R1 < ... < RL <= N, 1 <= C1 < ... < CK <= M and A[Ri][Cj]=1 for all 1 <= i <= L, 1<= j <= K. Here A[r][c] is the c-th element of the r-th row of considered rectangular grid.

Why does Chef call some (K+L)-tuple of numbers by the window? Just mark all points (Ri,Cj) (1 <= i <= L, 1<= j <= K) on the plane and join by line segments all pairs of points that has equal abscises or ordinates and you will see that this picture is like a window.

Now Chef considers some particular N x M grid and wants to calculate the total number of (L, K)-windows in this rectangular grid. Help him. Since this number can be very large calculate the result modulo 1000000080798150871.

Input

The first line contains a single positive integer T <= 100, the number of test cases. T test cases follow. The first line of each test case contains four positive integers N, M, L, K, where L, N <= 1000, K, M <=3. Next N lines describe the rectangular grid considered by Chef. Each of these lines contains M symbols. Every symbol is either one or zero.

Output

For each test case, output a single line containing the total number of (L, K)-windows for the given grid modulo 1000000080798150871.

Example

Input:
2
3 2 2 1
11
01
10
3 3 2 2
111
101
111

Output:
2
5

Explanation

In the first case it is just the number of pairs of cells with value 1 that have the same column number.

In the second case we have the following (2, 2)-windows:
(First row, Second row, First column, Third column)
(First row, Third row, First column, Second column)
(First row, Third row, First column, Third column)
(First row, Third row, Second column, Third column)
(Second row, Third row, First column, Third column)

Author: anton_lunyov
Date Added: 15-01-2011
Time Limit: 1 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

Grading is a bit slow today,

pr0ton @ 23 Jan 2011 10:18 PM

Grading is a bit slow today, isnt it?

Is the modulo value correct ?

Corrupted @ 23 Jan 2011 10:41 PM

Is the modulo value correct ? I am getting a warning in my compiler that it is too large

L, N <= 1000, K, M <=3. so

cgy4ever @ 23 Jan 2011 10:44 PM

L, N <= 1000, K, M <=3.

so what is the min possible value of them?

to ChenGaoyuan Look at the

anton_adm @ 23 Jan 2011 10:47 PM

to ChenGaoyuan

Look at the phrase "four positive integers N, M, L, K"

wtf? why such big mod :/

pdwd @ 23 Jan 2011 11:29 PM

wtf? why such big mod :/

Links for these problems in

pdwd @ 24 Jan 2011 12:51 AM

Links for these problems in practice section don't work.

All problems have been made

pdwd @ 24 Jan 2011 01:05 AM

All problems have been made available in the practice section.

Links don't work.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions