34174번 - 동우가 눈을 뜨면 해가 떠있는 이유는? 점수

문제

동우가 눈을 뜨면 해가 떠있는 이유는? Noon이라서라고 생각하셨나요? 그냥 늦잠이 동우의 패시브라서라고 생각하셨나요?

그것도 맞긴 하지만, 새벽이나 밤늦게 일어나지 않는 한 일반적으로 눈을 뜨면 해가 떠 있습니다.

MatKor Cup이 총 7ドル$회가 진행되며 이제 동우와 재우, 종우는 MatKor 최고참이 되어 후배들에게 여러 병장놀이를 하는 재미로 살고 있다. 세 명은 어느 날 해의 그림을 보고 해가 정$N$각형 처럼 생겼다고 생각하며 다음 놀이를 만들었다.

해는 정$N$각형처럼 생겼다.

동우는 길이 $N$의 순열 하나를 랜덤으로 고른다. 이때, 모든 $N!$가지의 순열 중 하나를 동일한 확률로 고른다.

재우는 정$N$각형 모양 종이의 한 점을 동일한 확률로 골라, 그 점부터 시계방향으로 동우가 정한 순열대로 점들에 번호를 부여한다.

종우는 모든 $i$번과 $i+1$번 꼭짓점을 지나는 선분을 그린다. 이때, $N$번과 1ドル$번도 연결한다. 만약, 이미 정$N$각형 모양 종이의 한 변을 이룬다면 그리지 않는다.

이제 가장 먼저 눈에 보이는 후배에게 이 선분을 따라 종이를 자르게 시킨다.

불의를 참을 수 없던 세진이는 이 놀이의 흥을 깨고 싶어 한다. 세진이는 가능한 어떤 $N$이 정해졌을 때, 최종적으로 나누어지는 종이 조각 개수의 기댓값을 구하고 싶다. 세진이를 도와 $N$이 1ドル$부터 10ドル,円 000$까지 각각의 경우에 대해 최종적으로 나누어지는 종이 조각 개수의 기댓값을 구해보자.

입력

첫 번째 줄에 문자열 Goodbye가 주어진다.

두 번째 줄에 문자열 So Long이 주어진다.

세 번째 줄에 문자열 MatKor Cup!이 주어진다.

출력

첫 번째 줄부터 10ドル,円 000$줄에 걸쳐 $N=1$부터 $N=10,円 000$까지 정답을 998ドル,円 244,円 353$으로 나눈 나머지를 출력한다. 단, $N\le 2$인 경우 정$N$각형이 존재하지 않으므로 대신 -1을 출력하라.

기약 분수 $\frac{p}{q}(p\ge 0,q>0,\gcd(p,q) =1)$를 $M$으로 나눈 나머지는 $q^{-1}$가 $q\cdot q^{-1}\equiv 1\pmod M$을 만족하는 정수, 즉 $q$의 $M$에 대한 모듈로 곱셈 역원일 때, $p\cdot q^{-1}\pmod M$로 정의한다. 만약 정수일 경우 $q=q^{-1}=1$이므로 $p\pmod M$를 의미한다.

주어진 조건 내에서 기댓값이 정수 혹은 유리수임을 증명할 수 있으며, 유리수의 경우 기약분수에서 분모가 998ドル,円 244,円 353$의 배수가 아닌 경우만 주어짐이 보장된다.

제한

각 $N$에 대해 정답이 맞은 개수 당 0ドル.01$점을 부여한다.

단, 출력이 10ドル,円 000$개의 정수가 아닌 경우나 $-1$ 이상 998ドル,円 244,円 353$ 미만의 범위를 벗어나는 경우 틀렸습니다를 받을 수 있으므로, 답을 구하지 못한 $N$도 정수를 출력하자.

노트

이 문제의 시간 제한이 1ドル.24$초인 이유는 동우의 생일이 1ドル$월 24ドル$일이기 때문이다.