Data je matrica dimenzija $R\times C$. Za niz podmatrica $P_1,P_2,\cdots,P_N$ kažemo da je adekavatan ako se u preseku svih ovih podmatrica barem $K$ polja matrice. Vaš cilj je da odredite broj dobrih nizova podmatrica po modulu $1000000007$. Dva niza se smatraju različita ukoliko se za bilo koje $i\le N$ razlikuju $i$-ti elementi tih nizova.

Opis ulaza

U prvoj i jedinoj liniji standardnog ulaza se nalaze $4$ prirodna broja $N,R,C,K$ ($N\le10^6$, $R,C\le5000$, $K\le R\cdot C$)

Opis izlaza

U prvoj i jedinoj liniji standardnog izlaza ispisati jedan broj: broj različitih dobrih nizova dužine $N$ po modulu $1000000007$

Primer ulaza

2 2 3 4

Primer izlaza

7

Objašnjenje primera

Postoji $7$ dobrih nizova pravougaonika. Ako je $Z_1$ matrica u reseku oba reda i prve dve kolone, $Z_2$ matrica u reseku oba reda i poslednje dve kolone i $Z_3$ ceo pravougaonik, onda su dobri nizovi $(Z_1,Z_1),(Z_1,Z_3),(Z_3,Z_1),(Z_2,Z_2),(Z_2,Z_3),(Z_3,Z_2),(Z_3,Z_3)$.