cercetasi

Ionuț s-a înscris recent într-o trupă de cercetași și se pregătește pentru prima sa expediție. Trupa din care face parte Ionuț este formată din $N$ membri, numerotați cu numere naturale de la $1$ la $N$. Pentru expediție, trupa trebuie să se împartă în mai multe patrule, fiecare membru $i$ trebuie să facă parte din exact o patrulă. Între cercetașii din trupă există niște tensiuni, astfel cercetașul $i$ și cercetașul $j$ (cu $i \neq j$) pot face parte din aceeași patrulă doar dacă $|i - j| \geq r$ (unde $|x|$ reprezintă valoarea absolută a numărului $x$).

Cerințe

Ionuț, fiind foarte pasionat de numere, se întreabă în câte moduri se pot forma patrule pentru expediție, știind că cercetașul șef vrea ca trupa să se împartă în cel puțin $a$ patrule și cel mult $b$ patrule. Două moduri $A$ și $B$ de a forma patrulele se consideră diferite dacă au un număr diferit de patrule sau dacă există un cercetaș $k$ (cu $1 \leq k \leq N$) astfel încât echipa din care face parte $k$ în modul $A$ este diferită de cea din modul $B$. Cum acest număr poate fi foarte mare, se cere afișarea lui modulo $10^9 + 7$.

Date de intrare

Fișierul de intrare cercetasi.in conține o singură linie pe care se află, în ordine, numerele $N$, $r$, $a$ și $b$ cu semnificația din enunț. Numerele sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire cercetasi.out va conține, pe o singură linie numărul de moduri în care se pot forma patrulele pentru expediție, modulo $10^9 + 7$.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$
• $1 \leq r \leq a \leq b \leq N$

Exemplul 1

cercetasi.in

4 1 2 2

cercetasi.out

7

Explicație

În primul exemplu avem $n = 4$ cercetași, oricare doi putând face parte din aceeași patrulă, deoarece $r = 1$. Cum $a = b = 2$ trebuie să aflăm numărul de moduri de a împărți cercetașii în două patrule. Avem următoarele 7 moduri:

$(\{1\}, \{2, 3, 4\})$; $(\{2\}, \{1, 3, 4\})$; $(\{3\}, \{1, 2, 4\})$; $(\{4\}, \{1, 2, 3\})$; $(\{1, 2\}, \{3, 4\})$; $(\{1, 3\}, \{2, 4\})$; $(\{1, 4\}, \{2, 3\})$.

Exemplul 2

cercetasi.in

5 2 2 3

cercetasi.out

8

Explicație

În al doilea exemplu avem $n = 5$ cercetași, oricare doi alăturați neputând face parte din aceeași patrulă, deoarece $r = 2$. Avem $a = 2$ și $b = 3$, deci trebuie să aflăm numărul de moduri de a împărți cercetașii în două sau trei patrule.

Pentru a împărți cercetașii în două patrule avem o posibilitate:

$(\{1, 3, 5\}, \{2, 4\})$.

Observăm aici că o împărțire de forma $(\{1, 3, 4\}, \{2, 5\})$ nu este posibilă deoarece $1$ și $4$ fac parte din aceeași patrulă, dar $|4 - 3| = 1 < r = 2$.

Trebuie acum să aflăm numărul de moduri de a împărți cercetașii în trei patrule. Avem 7 posibilități:

$(\{1\}, \{2, 4\}, \{3, 5\})$; $(\{1, 3\}, \{2, 4\}, \{5\})$; $(\{1, 3\}, \{2, 5\}, \{4\})$; $(\{1, 3, 5\}, \{2\}, \{4\})$; $(\{1, 4\}, \{2, 5\}, \{3\})$;

$(\{1, 5\}, \{2, 4\}, \{3\})$; $(\{1, 4\}, \{2\}, \{3, 5\})$.

Astfel, sunt în total $1 + 7 = 8$ posibilități.

Exemplul 3

cercetasi.in

97 3 8 29

cercetasi.out

987428607