창호의 유학 준비

창호는 외국으로 유학을 준비하면서 요즘 외국어 공부에 매진하고 있다. 재우는 창호를 돕고자 서로 다른 외국어 단어 $X$개가 적힌 리스트를 선물했다. 그런데 이 리스트의 단어 중 $Y$개는 창호가 이미 아는 단어였다. 창호는 이런 단어를 Well-Known 단어라고 부르기로 했다. 창호는 효율적으로 공부하려고 Well-Known 단어에 대해서는 같은 단어를 $Z$번 이상 연속으로 공부하지 않기로 규칙을 정했다. 재우는 이 규칙을 듣고, 창호가 리스트의 단어를 공부하는 전체 경우의 수가 궁금해졌다.

공부 한 번에는 단 하나의 단어만 공부한다고 하자. 창호가 외국어 공부를 하는 횟수 $N$, 리스트에 포함된 단어의 개수 $X$, Well-Known 단어의 개수 $Y$, Well-Known 단어 공부에 대한 제한 $Z$가 주어질 때, 창호가 리스트의 단어를 공부하는 전체 경우의 수를 구하라. 같은 단어를 여러 번 공부할 수도 있고, 공부하지 않는 단어가 있을 수도 있다.

첫 번째 줄에 네 정수 $N$ ($1 \leq N \leq 10^{18}$), $X$ ($1 \leq X \leq 10^{18}$), $Y$ ($1 \leq Y \leq X$), $Z$ ($1 \leq Z \leq 10^{3}$)가 공백을 사이에 두고 주어진다.

창호가 리스트의 단어를 공부하는 전체 경우의 수를 $1\,000\,000\,007$로 나눈 나머지를 출력한다. 답이 커질 수 있기 때문이다.