운세 점치기

유명한 점술가가 타로 카드 여러 장과 6면체 주사위를 가지고 있다. 그녀는 주사위로 카드 한 장을 고르고, 그 카드가 당신의 미래를 알려 준다.

처음에 카드들은 왼쪽에서 오른쪽으로 한 줄로 놓여 있다. 주사위를 던지면 1부터 6까지의 눈 중 하나가 같은 확률로 나온다. 나온 눈을 $x$라고 하면, 왼쪽에서 $x$번째 카드와 그 뒤로 6장마다 있는 카드, 즉 $(x + 6k)$번째 카드($k = 0, 1, 2, \dots$)를 모두 제거한다. 그다음 남은 카드들을 왼쪽으로 밀어 빈틈을 없앤다. 남은 카드 수가 $x$보다 적으면 카드를 제거하지 않는다. 이 제거와 이동 과정은 카드가 한 장 남을 때까지 반복된다.

그림 G.1은 주사위 눈이 2일 때 카드를 제거하고 미는 과정을 보여 준다.

그림 G.1. 카드 제거와 이동

타로 카드의 초기 장수가 주어진다. 처음 놓인 각 카드가 마지막까지 남을 확률을 구하라.

첫 줄에 타로 카드의 장수를 나타내는 정수 $n$이 주어진다. $2 \le n \le 3 \times 10^5$ 이다.

$n$개의 줄을 출력한다. $i$번째 줄에는 왼쪽에서 $i$번째 카드가 마지막까지 남을 확률로부터 다음과 같이 정해지는 정수를 출력한다.

이 확률은 기약분수 $a/b$로 나타낼 수 있으며, $b$는 소수 $998\, 244\, 353 = 2^{23} \times 7 \times 17 + 1$로 나누어떨어지지 않는다. $bc \equiv a \pmod {998\, 244\, 353}$ 이고 $0 \le c < 998\, 244\, 353$ 을 만족하는 정수 $c$가 유일하게 존재한다. 이 정수 $c$를 출력한다.

입력 예시 1의 경우, 모든 카드가 마지막까지 남을 확률은 $1/3$ 으로 같다.

입력 예시 2의 경우, 가장 왼쪽 카드를 생각해 보자. 이 카드가 남으려면 처음 나온 눈이 1이 아니어야 한다. 1이 아닌 눈이 나오면 카드 6장이 남고, 이 카드들은 각각 같은 확률로 마지막까지 남는다. 따라서 가장 왼쪽 카드가 남을 확률은 $(5/6) \times (1/6) = 5/36$ 이다. 가장 오른쪽 카드도 같은 논리가 성립한다. 나머지 카드들의 확률은 모두 같으며, 그 값은 $(1 - 2 \times 5/36)/5 = 13/90$ 이다.