Ω Batch Compilation commands

이제 조금 더 어려운 문제를 해결해 보자. 당신은 지금 $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 $일 확률을 출력한다. 정확한 판별을 위해, 답을 기약분수로 나타내었을 때 가 된다면, 을 대신 출력하도록 한다. $b^{-1}$은 $b$의 모듈러 곱셈에 대한 역원이다. 이 문제에서는 가능한 모든 입력에 대해 답이 존재한다.

입출력 예제

입력

3
2
5
3

출력

903225813