주사위 놀이의 승리 확률

$P$면체 주사위를 굴린다. 각 면에는 $1$ 이상 $P$ 이하의 자연수가 하나씩 적혀 있고, 한 번 굴렸을 때 각 면이 나올 확률은 모두 같다.

다음 놀이를 한다.

• 처음에 수 $K$를 가지고 있다.
• 가지고 있는 수가 $0$이거나 $N$이면 놀이를 끝낸다.
• 그렇지 않으면 주사위를 한 번 굴린다. 나온 수가 $Q$ 이하이면 가지고 있는 수에서 $1$을 빼고, $Q$보다 크면 $1$을 더한다. 그다음 두 번째 규칙으로 돌아가 반복한다.

놀이가 끝났을 때 가지고 있는 수가 $N$일 확률을 구하는 프로그램을 작성하라.

첫째 줄에 정수 $P$가 주어진다. ($1 \le P \le 100$)

둘째 줄에 정수 $Q$가 주어진다. ($0 \le Q \le P$)

셋째 줄에 정수 $N$이 주어진다. ($1 \le N \le 100$)

넷째 줄에 정수 $K$가 주어진다. ($0 \le K \le N$)

놀이가 끝났을 때 가지고 있는 수가 $N$일 확률을 출력한다. 정확하게 판정하기 위해, 답을 기약분수로 나타낸 것을 $a/b$라 할 때 $(a \times b^{-1}) \bmod 1{,}000{,}000{,}007$을 대신 출력한다. $b^{-1}$은 $1{,}000{,}000{,}007$을 법으로 하는 $b$의 곱셈 역원이다. 주어지는 모든 입력에 대해 답이 존재한다.