27308번 - 창호의 유학 준비

문제

외국으로의 유학을 준비하고 있는 창호는 요즘 외국어 공부에 매진하고 있다. 이를 도와주고 싶었던 재우는 창호에게 서로 다른 외국어 단어 $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}$), Well-Known 단어의 개수 $Y$ (1ドル \leq Y \leq X$), Well-Known 단어 공부에 대한 제한 $Z$ (1ドル \leq Z \leq 10^3$)가 공백을 사이에 두고 주어진다. $N,ドル $X,ドル $Y,ドル $Z$는 모두 정수로 주어진다.

출력

창호가 재우가 준 리스트의 단어들을 공부하는 전체 경우의 수를 출력한다. 단, 답이 커질 수 있으므로 1ドル,000円,000円,007円$로 나눈 나머지를 출력한다.

제한

힌트