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 𝑁 membri, numerotați cu numere naturale de la 1 la 𝑁. Pentru expediție, trupa trebuie să se împartă în mai multe patrule, fiecare membru 𝑖 trebuie să facă parte din exact o patrulă. Între cercetașii din trupă există niște tensiuni, astfel cercetașul 𝑖 și cercetașul 𝑗 (cu 𝑖 ≠ 𝑗) pot face parte din aceeași patrulă doar dacă |𝑖 − 𝑗| ≥ 𝑟 (unde |𝑥| reprezintă valoarea absolută a numărului 𝑥).

Cerința

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 𝑎 patrule și cel mult 𝑏 patrule. Două moduri 𝐴 și 𝐵 de a forma patrulele se consideră diferite dacă au un număr diferit de patrule sau dacă există un cercetaș 𝑘 (cu 1 ≤ 𝑘 ≤ 𝑁) astfel încât ehipa din care face parte 𝑘 în modul 𝐴 este diferită de cea din modul 𝐵. Cum acest număr poate fi foarte mare, se cere afișarea lui modulo 109 + 7.

Date de intrare

Fișierul de intrare cercetasi1.in conține o singură linie pe care se află, în ordine, numerele 𝑁, 𝑟 𝑎 și 𝑏 cu semnificația din enunț. Numerele sunt separate prin câte un spațiu.

Date de ieșire

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

Restricții și precizări

• 1 ≤ 𝑁 ≤ 100 000
• 1 ≤ 𝑟 ≤ 𝑎 ≤ 𝑏 ≤ 𝑁

Subtaskuri

• 4 1 ≤ 𝑁 ≤ 10, 𝑎 = 𝑏, 𝑟 = 1
• 6 1 ≤ 𝑁 ≤ 10
• 8 10 < 𝑁 ≤ 500, 𝑏 = 2
• 6 500 < 𝑁 ≤ 5 000, 𝑎 = 𝑁 − 1
• 7 500 < 𝑁 ≤ 5 000, 𝑟 = 1
• 9 500 < 𝑁 ≤ 5 000
• 5 1 ≤ 𝑏 · 𝑁 ≤ 5 000 000, 𝑟 = 1
• 6 1 ≤ 𝑏 · 𝑁 ≤ 5 000 000
• 10 5 000 < 𝑁 ≤ 100 000, 0 ≤ 𝑏 − 𝑎 ≤ 100, 𝑟 = 1
• 13 5 000 < 𝑁 ≤ 100 000, 0 ≤ 𝑏 − 𝑎 ≤ 100
• 5 𝑟 = 𝑎 − 1 sau 𝑟 = 𝑎
• 21 Fără restricții suplimentare

Exemplul 1

cercetasi1.in

4 1 2 2

cercetasi1.out

7

Exemplul 2

cercetasi1.in

5 2 2 3

cercetasi1.out

8

Exemplul 3

cercetasi1.in

97 3 8 29

cercetasi1.out

987428607

Explicație

În primul exemplu avem 𝑛 = 4 cercetaşi, oricare doi putând face parte din aceeaşi patrulă, deoarece 𝑟 = 1. Cum 𝑎 = 𝑏 = 2 trebuie să aflăm numărul de moduri de a impă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}).

În al doilea exemplu avem 𝑛 = 5 cercetaşi, oricare doi alăturaţi neputând face parte din aceeași patrulă, deoarece 𝑟 = 2. Avem 𝑎 = 2 şi 𝑏 = 3, deci trebuie să aflăm numărul de moduri de a impă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 3 și 4 fac parte din aceeași
patrulă, dar |4 − 3| = 1 < 𝑟 = 2.

Trebuie acum să aflăm numărul de moduri de a impă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.