제비 Batch Compilation commands

시간이 많은 그는 제비 뽑기를 계속하고 있다. 그냥 아무것도 없이 하다 보니 재미가 없어서 제비를 뽑고 난 후에 어떤 제비를 뽑았는지 에 따라 지켜야 하는 규칙을 만들어 신선한 제비 뽑기를 하려고 한다.

그는 지금 끝을 빨간색으로 칠한 제비를 $R $개, 초록색은 $G $개, 파란색은 $B $개를 만들었다. 이 제비들을 모두 색칠한 쪽이 보이지 않게 통에 넣고 잘 섞은 다음에 제비를 하나씩 뽑을 것이다. 그는 제비를 매우 잘 섞기 때문에 모든 제비는 뽑힐 확률이 동일해진다. 뽑은 제비의 색에 따라 다음과 같은 일을 한다.

1. 빨간 제비를 뽑은 경우에는 뽑은 제비를 쓰레기통에 버린다.
2. 초록 제비를 뽑은 경우에는 뽑은 제비를 다시 통에 넣고 제비들을 잘 섞는다.
3. 파란 제비를 뽑은 경우에는 뽑은 제비를 다시 통에 넣고 제비들을 잘 섞는다. 만약 파란 제비를 뽑은 횟수가 $K $번이 되면 제비 뽑기를 그만 두고 잠이나 자러 가도록 한다.

그가 잠을 자러 갈 때까지 뽑게 되는 제비 개수의 기댓값을 구하는 프로그램을 작성하라.

입력

첫 번째 줄에는 테스트 케이스의 개수 $T(1 \le T \le 10^{3})$가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 그가 가진 빨간 제비의 개수 $R$, 초록 제비의 개수 $G$, 파란 제비의 개수 $B$, 파란 제비를 몇 번 뽑아야 잠을 자러 가게 되는지를 나타내는 $K $가 공백으로 구분되어 주어진다. 각 수는 모두 1이상의 자연수이다.

부분문제

출력

각 테스트 케이스마다 한 줄에 그가 잠을 자러 갈 때까지 뽑게 되는 제비 개수의 기댓값을 출력한다. 정확한 판별을 위해, 답을 기약분수로 나타내었을 때 가 된다면, 을 대신 출력하도록 한다. $b^{-1}$은 $b$의 모듈러 곱셈에 대한 역원이다. 이 문제에서는 가능한 모든 입력에 대해 답이 존재한다.

입출력 예제

예제 1

입력

4
1 1 1 1
1 2 3 4
1000 1000 1 1000
50000 50000 50000 10000000

출력

500000006
569010428
490804548
595034885

예제 2

입력

4
9 9 9 1
9 9 9 2
9 9 9 4
9 9 9 1000

출력

300000005
470000009
700700016
814176661

첫 번째 입력은 1번 부분 문제에 속하지 않음에 유의하라.

첫 번째 입력의 첫 번째 테스트 케이스의 답은 $5/2$를 나타낸다.

두 번째 입력은 1번 부분 문제에 속한다.