Whole submatrix

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 (R_{1}, ..., R_{L}, C_{1}, ..., C_{K}) such that 1 <= R_{1} < ... < R_{L} <= N, 1 <= C_{1} < ... < C_{K} <= M and A[R_{i}][C_{j}]=1 for all 1 <= i <= L, 1<= j <= K. Here A[r][c] is the cth element of the rth row of considered rectangular grid.
Why does Chef call some (K+L)tuple of numbers by the window? Just mark all points (R_{i},C_{j}) (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 
Tester:  friggstad 
Editorial  http://discuss.codechef.com/problems/WINDOW2 
Tags  anton_lunyov cook06 easy 
Date Added:  15012011 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.4, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions