Problem 4020: Grădina

Cerință

Keiko Hamada a fost angajată să amenajeze noua grădină Zen a familiei Nomizu. Domnul Nomizu vrea să folosească noua grădină pentru a medita. Din păcate, el nu își poate goli mintea decât dacă grădina respectă o serie de condiții.

Grădina domnului Nomizu trebuie să conțină un singur tip de copac, și anume cireșul. Un cireș poate fi reprezentat ca un arbore cu rădăcină. Definim o creangă a cireșului drept o muchie din reprezentarea sa ca arbore. (În această problemă, tulpina este considerată o creangă.).

În fiecare primăvară, cireșii înfloresc. Ei produc câte o floare în vârful fiecărei crengi care nu se continuă cu nicio altă creangă. Mai exact, florile apar în fiecare nod frunză al reprezentării cireșului ca arbore.

Domnul Nomizu vrea o grădină cu cel mult $N$ cireși, așezați pe un singur rând, care să aibă în total $M$ crengi. Mai mult, atunci când înfloresc, cireșii trebuie să aibă între $st$ și $dr$ flori. Presupunem că toți cireșii înfloresc în același timp.

Mai formal, o amenajare a grădinii domnului Nomizu este o colecție ordonată de cel mult $N$ arbori cu rădăcină $(A_1, A_2,...,A_k)$ cu $1 \leq k \leq N$ , cu $\text{nrMuchii}(A_1)+\text{nrMuchii}(A_2)+...+\text{nrMuchii}(A_k) = M$ (aici $\text{nrMuchii}(T) =$ numărul de muchii ale arborelui $T$ ) și cu $st \leq \text{nrFrunze}(A_1)+\text{nrFrunze}(A_2)+...+\text{nrFrunze}(A_k) \leq dr$ (aici $\text{nrFrunze}(T)=$ numărul de frunze ale arborelui $T$ ; se numește o frunză a arborelui un nod care nu are copii). Două aranjări $A=(A_1, A_2,...,A_k)$ și $B=(B_1, B_2,...,B_p)$ ale grădinii se consideră diferite dacă: $k \neq p$ sau $k = p$ și există un indice $1 \leq i \leq k$ cu proprietatea că arborii $A_i$ și $B_i$ nu sunt identici.

Fie $A$ și $B$ doi arbori cu rădăcină. Dacă $\text{nrMuchii}(A)=\text{nrMuchii}(B)=0$ , atunci spunem că $A$ și $B$ sunt identici. Dacă $\text{nrMuchii}(A)>1$ și $\text{nrMuchii}(B)>1$ considerăm $(copilA_{1},copilA_2,...,copilA_k)$ și $(copilB_1,copilB_2,...,copilB_p)$ listele ordonate de copii ale rădăcinii arborelui $A$ și respectiv $B$ . $A$ și $B$ sunt identici dacă $k=p$ și $S_{copilA_1}$ identic cu $S_{copilB_1}$ $,$ $S_{copilA_2}$ identic cu $S_{copilB_2}$ $, ...,$ $S_{copilA_k}$ identic cu $S_{copilB_k}$ (aici am notat cu $S_x$ subarborele cu rădăcina în nodul $x$ ). În rest, spunem că $A$ și $B$ nu sunt identici.

În figura de mai jos, conform definiției, cei doi arbori sunt identici.

În figura de mai jos, conform definiției, cei doi arbori nu sunt identici.

Keiko vă întreabă în câte moduri ar putea planta cireșii domnului Nomizu, astfel încât să-i satisfacă pretențiile. Pentru că acest număr poate fi foarte mare, Keiko se va mulțumi cu valoarea sa modulo $10^{9}+7$ .

Date de intrare

Pe prima linie se găsesc numerele $N, M, st, dr$ în această ordine cu semnificația din enunț.

Date de ieșire

Pe prima linie se va afișa un singur număr natural, reprezentând numărul de moduri în care Keiko îi poate aranja grădina domnului Nomizu (modulo $10^9+7$ ).