27734번 - 끝말잇기

흰곰과 흑곰은 토끼에게 $N$개의 단어가 있는 사전을 받았다. 흰곰과 흑곰은 끝말잇기를 즐겨 한다. 끝말잇기는 두 곰이 번갈아가며 사전에 있는 단어를 말하는 놀이이다. 끝말잇기를 할 때는 직전에 다른 곰이 말한 단어의 마지막 글자로 시작하는 단어만 말할 수 있다. 가능한 단어가 적어도 하나 있다면 곰은 그 중 하나를 무작위로 말한다. 각각의 단어를 말할 확률은 모두 같다. 가능한 단어가 하나도 없다면 끝말잇기를 끝낸다. 마지막으로 단어를 말한 곰이 이긴다.

사전에 있는 한 단어를 여러 번 말할 수 있다. 이로 인해 끝말잇기가 끝나는 것이 불가능 할 수도 있다. 토끼는 곰이 단어를 말할 때마다 끝말잇기가 끝나는 것이 가능한지 불가능한지 판단한다. 두 곰이 이후에 어떤 단어를 말해도 끝말잇기가 끝날 수 없다면 토끼가 끝말잇기를 끝낸다. 이때는 토끼가 이긴다.

흰곰이 사전의 $i$ 번째 단어를 말하는 것으로 끝말잇기를 시작해서 흰곰이 이길 확률을 $\alpha_i$, 흑곰이 이길 확률을 $\beta_i$, 토끼가 이길 확률을 $\gamma_i$, 끝말잇기가 끝날 때까지 두 곰이 단어를 말하는 횟수의 기댓값을 $\delta_i$로 정의한다. 흰곰, 흑곰, 토끼는 수학적으로 계산한 $\alpha ,\beta ,\gamma ,\delta$ 값과 직접 끝말잇기를 해서 계산한 $\hat\alpha ,\hat\beta ,\hat\gamma ,\hat\delta$ 값을 비교해보려 한다.

$1$부터 $N$까지의 정수 $i$에 대해 $\alpha_i,\beta_i,\gamma_i,\delta_i$를 구하시오.

첫 번째 줄에 사전에 있는 단어의 개수 $N$이 주어진다. $(1\le N\le 2\times 10^5)$

두 번째 줄부터 $N$개의 줄에 걸쳐 $i+1$ 번째 줄에 사전의 $i$ 번째 단어 $w_i$가 주어진다. $(1\le\lvert w_i\rvert\le 10;$ $i\neq j\implies w_i\neq w_j)$ 모든 단어는 로마자 대문자로 이루어져 있다.

첫 번째 줄부터 $N$개의 줄에 걸쳐 $i$ 번째 줄에 $\alpha_i,\beta_i,\gamma_i,\delta_i$를 각각 $998\, 244\, 353$으로 나눈 나머지를 공백으로 구분하여 출력한다.

엄밀하게는 유리수 $\alpha_i,\beta_i,\gamma_i,\delta_i$에 대해 다음의 $R$을 구해야 한다. $P\ge 0,Q>0,\gcd(P,Q) =1$인 정수 $P,Q$에 대해 주어진 값을 $\frac{P}{Q}$로 나타낼 수 있다. 이때 $0\le R<998\, 244\, 353$인 정수 $R$에 대해 $R\times Q\equiv P\pmod{998\, 244\, 353}$이다. $R$이 유일하게 존재함이 보장된다.