지면 위에는 아래에서부터 위로 개의 대기층이 차례대로 존재한다. 번째 대기층의 반사율은 이다.
처음에 빛의 양 이 지면에 도달한다. 지면은 자신에게 도달한 빛을 모두 다시 위쪽으로 방출한다.
빛이 아래에서 위로 이동하다가 번째 대기층에 도달하면, 현재 빛의 양의 는 지면으로 다시 반사되고, 나머지는 위쪽으로 통과한다. 모든 대기층을 통과한 빛은 우주로 빠져나가 다시 돌아오지 않는다. 빛이 위에서 아래로 이동할 때는 모든 빛이 통과됨에 유의하라.
지면으로 반사된 빛은 다시 지면에 도달하고, 지면은 그 빛을 다시 위쪽으로 방출한다. 이 과정은 무한히 반복된다.
무한한 시간이 지난 뒤, 지면에 도달한 빛의 총량을 구하여라. 처음에 지면에 도달한 빛의 양 도 총량에 포함한다.
정답은 유리수가 될 수 있으므로, 정답을 기약분수 로 나타냈을 때 을 출력한다.
단, 은 의 에 대한 잉여역수이다.
잉여역수의 정의
이 문제의 정답은 정수가 아닐 수 있다. 따라서 정답을 기약분수 로 나타냈을 때, 를 출력한다.
여기서 은 의 잉여역수, 또는 모듈러 역원이다.
정수 의 에 대한 잉여역수란, 다음을 만족하는 정수 를 의미한다.
이때 를 이라고 쓴다.
예를 들어 일 때,
이므로 이다.
가 소수이고 가 의 배수가 아니라면, 페르마의 소정리에 의해
가 성립한다. 따라서 빠른 거듭제곱을 이용해 시간에 잉여역수를 구할 수 있다.
Input
입력은 다음과 같은 형식으로 주어진다.
Output
무한한 시간이 지난 뒤 지면에 도달한 빛의 총량을 로 나눈 나머지 형태로 출력한다.
정답을 기약분수 로 나타냈을 때, 을 출력해야 한다.
Constraints
- .
- ().
- 입력으로 주어지는 모든 값은 정수이다.
Subtasks
Samples
처음에는 만큼의 빛이 지면에 도달한다.
그 후 방출된 빛의 인 이 다시 지면에 도달하고, 그 다음에는 의 인 가 다시 지면에 도달한다.
따라서 총량은
이다.
이므로 정답은 이다.
해설
관리자가 작성한 해설을 별도 페이지에서 볼 수 있어요.