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)

见题面

见题面