번 방이 일렬로 놓여 있고, 이웃한 두 방 사이에는 문이 하나씩 있다. 번 문은 번 방과 번 방을 연결한다.
각 번 문에는 양의 정수 가 주어진다. 매분 번 문 중 하나가 선택되어 잠시 열렸다가 닫힌다. 이때 번 문은 의 확률로 선택된다.
따스는 처음에 번 방에 위치한다. 따스와 인접한 문이 열리면 따스는 즉시 그 문을 통해 이웃한 방으로 이동한다. 따스와 인접하지 않은 문이 열리면 따스는 현재 방에 그대로 머무른다.
따스는 번 방에 처음 도착할 때까지 이 과정을 반복한다. 각 에 대해, 과정이 끝나기 전까지 따스가 번 방에서 머무른 시간의 기댓값을 구하여라.
기댓값을 기약분수 로 나타냈을 때, 을 으로 나눈 나머지를 출력한다. 여기서 은 의 에 대한 곱셈 역원이다. 답은 가 의 배수가 아닌 유리수로 표현 가능함을 증명할 수 있다.
입력은 다음과 같은 형식으로 주어진다.
첫째 줄에 개의 정수를 공백으로 구분하여 출력한다. 번째 정수는 따스가 번 방에서 머무른 시간의 기댓값을 으로 나눈 나머지여야 한다.
따스가 번 방에서 머무르는 시간의 기댓값은 이다.
