독한 댓글
시간 제한1초메모리 제한1024 MB
댓글을 다운보트에 비례하는 확률로 하나씩 삭제할 때, 내가 쓴 N개의 댓글이 모두 지워질 때까지의 삭제 횟수 기댓값을 구한다.
문제
블로그에 개의 독한 댓글이 달려 있다. 그중 개는 당신이 쓴 댓글이고, 번째 댓글은 비추천 개를 받았다. 나머지 개 중 번째 댓글은 비추천 개를 받았다.
Mike는 다음 연산을 반복해서 댓글을 하나씩 지운다.
- 남아 있는 댓글 중 하나를 무작위로 골라 지운다. 정확히는 남아 있는 댓글이 받은 비추천 수를 라 하면, 번째 댓글을 의 확률로 고르고 지운다.
각 연산에서의 선택은 서로 독립이다.
Mike가 당신의 댓글을 모두 지울 때까지 수행할 연산 횟수의 기댓값을 구하시오. 답은 유리수이고, 평소처럼 으로 나눈 나머지를 출력하면 된다. 이 문제의 제약에서 그런 표현이 항상 가능함을 증명할 수 있다.
입력
첫째 줄에 정수 과 이 주어진다. ()
둘째 줄에 정수 이 주어진다. ()
셋째 줄에 정수 이 주어진다. (, )
출력
답을 출력한다.