Se dă o matrice A cu N linii și M coloane cu elemente numere naturale nu neapărat distincte. Pentru o submatrice definim mex-ul acesteia ca fiind cea mai mică valoare naturală nenulă care nu apare în aceasta.

Cerința

Să se calculeze produsul mex-urilor tuturor submatricelor având K linii și L coloane ale matricei A.

Date de intrare

Fișierul de intrare mexitate.in conține pe prima linie patru numere naturale N, M, K şi L separate printr-un spaţiu cu semnificația din enunț. Pe fiecare dintre următoarele N linii se află câte M numere naturale nenule, despărțite prin câte un spațiu, reprezentând valorile matricei.

Date de ieșire

Fișierul de ieșire mexitate.out va conține un singur număr natural reprezentând produsul mex-urilor tuturor submatricelor având K linii și L coloane ale matricei modulo 1 000 000 007.

Restricții și precizări

• 1 ≤ N * M ≤ 400 000
• 1 ≤ K ≤ N
• 1 ≤ L ≤ M
• 1 ≤ A[i][j] ≤ N * M, 1 ≤ i ≤ N, 1 ≤ j ≤ M
• Pentru 20% din punctajul total există teste cu 1 ≤ N, M ≤ 50
• Pentru alte 20% din punctajul total există teste cu 1 ≤ N, M ≤ 630

Exemplu:

mexitate.in

3 4 2 3
1 2 3 2
2 3 1 4
1 1 2 6

mexitate.out

400

Explicație

N = 3, M = 4, K = 2 și L = 3
Submatricile cu două linii și trei coloane sunt:
1 2 3 cu mex-ul 4
2 3 1

2 3 2 cu mex-ul 5
3 1 4

2 3 1 cu mex-ul 4
1 1 2

3 1 4 cu mex-ul 5
1 2 6

Produsul tuturor mex-urilor este: 4 * 5 * 4 * 5 = 400
400 % 1 000 000 007 = 400