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)~.