Cerința

O culegere de probleme de informatică conține n probleme, dintre care m sunt probleme ușoare. Bubu dorește să rezolve k probleme din culegere. În câte moduri poate alege Bubu cele k probleme, astfel încât între cele k probleme alese să existe cel puțin s probleme ușoare? Deoarece numărul obținut poate fi foarte mare, valoarea acestuia trebuie precizată modulo 1000003.

Date de intrare

Fișierul de intrare probleme.in conține patru numere naturale n (numărul problemelor din culegere), m (numărul problemelor ușoare), k (numărul de probleme care trebuie rezolvate) și s (numărul minim de probleme ușoare din cele k), despărțite prin câte un spațiu.

Date de ieșire

Fișierul de ieșire probleme.out va conține pe prima linie un număr natural reprezentând numărul de moduri în care poate alege Bubu cele k probleme, astfel încât între acestea să existe cel puțin s probleme ușoare. Acestă valoare trebuie precizată modulo 1000003.

Restricții și precizări

• 1 ≤ s ≤ m ≤ n ≤ 100000 (numere naturale)
• 1 ≤ k ≤ n

Exemplu:

probleme.in

6 4 3 2

probleme.out

16