Problem L
Theodor, Trollkarlen

Detta problem bygger på problemet Trollkarlen Theodor.

Ondskefulla Olle, som är ytterst ansvarig för all ondska, har tröttnat på att Theodor alltid förstör allting. Nu har Olle kommit på en ny ondskefull plan, och för att sätta den i verket måste han uppehålla Theodor. Till sitt förfogande har han $N$ monster, och eftersom han är så enormt mäktig kan han ge dessa monster olika antal liv. Olle vill nu räkna antalet sätt han kan ge olika mängder liv till sina olika monster, så att Theodor behöver avfyra exakt $K$ magiska explosioner för att besegra alla monster. Enda kravet på antalet liv för ett monster är att det ska vara större än $0$.

Precis som i problemet Trollkarlen Theodor skadar Theodor monster genom att sikta på ett särskilt monster och avfyra en explosion. Monstret han siktar på förlorar då $S$ liv, och sedan förlorar alla monster (även det han siktade på) $A$ liv var. Ett monster är besegrat om det har 0 eller färre liv. Theodor väljer hur han siktar på monster så att han minimerar antalet explosioner han behöver avfyra.

Indata

Den första raden innehåller fyra tal, $N, K, S, A$ ($1 \leq N,K,S \leq 2\cdot 10^5$, $0 \leq A \leq 2\cdot 10^5$), vilket är de fyra talen som beskrivits ovan.

Utdata

Skriv ut antalet sätt Olle kan ge liv till sina monster så att Theodor behöver avfyra exakt $K$ explosioner för att besegra alla. Eftersom detta tal kan bli väldigt stort ska du skriva ut det modulo $(10^9+7)$.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av exempelfall

I exempelfall 1 finns det ett monster, och de möjliga liv det kan ha så att Theodor besegrar det med exakt en explosion är 1, 2, 3, 4, 5.

I exempelfall 2 finns det 10 fördelningar av monsterliv så att Theodor besegrar båda med exakt två explosioner. Dessa är:

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

1 1 5 0

5

2 2 1 1

10

10 20 30 40

435462573