Það eru $U + T + P + C$ spil. Meðal þeirra eru $U$ spil með mynd af einhyrningi á framhliðinni, $T$ spil með tígrisdýri, $P$ spil með pöndu og $C$ spil með ketti. Í upphafi liggja öll spilin á grúfu og ómögulegt er að greina hvaða mynd er á hverju spili.
Þú munt spila leik með þessum spilum. Leikurinn samanstendur af nokkrum umferðum. Í hverri umferð velur þú að framkvæma annaðhvort Aðgerð A eða Aðgerð B:
- Aðgerð A: Veldu eitt af spilunum sem liggja á grúfu af handahófi með jöfnum líkum og snúðu því við. Ef dregna spilið sýnir einhyrning, tígrisdýr eða pöndu heldur þú áfram í næstu umferð og leikurinn heldur áfram. Spilið sem snúið var við helst á réttunni. Ef dregna spilið sýnir kött lýkur leiknum samstundis. Í því tilfelli verða stigin þín $0$.
- Aðgerð B: Ljúktu leiknum samstundis. Látum $u$ vera fjölda spila á réttunni sem sýna einhyrning og $t$ vera fjölda spila á réttunni sem sýna tígrisdýr. Stigin þín verða $2u + t$.
Finndu væntigildi stiganna þegarbestu stefnu er fylgt til að hámarka væntigildi stiganna, modulo $998244353$.
Athugasemd um væntigildi modulo $998244353$
Sanna má að væntigildið í þessu verkefni er alltaf ræð tala. Að auki, samkvæmt skorðum þessa verkefnis, þegar væntigildið er sett fram sem óstyttanlegt brot $\frac{x}{y}$, er tryggt að $y$ sé ekki deilanlegt með $998244353$. Því er til nákvæmlega ein heiltala $z$ ($0 \le z < 998244353$) þannig að $y \cdot z \equiv x \pmod{998244353}$. Þú átt að prenta þetta $z$.
Inntak
Inntakið er gefið úr staðalinntaki á eftirfarandi sniði:
$$U \quad T \quad P \quad C$$
- Öll inntaksgildi eru heiltölur.
- $1 \le U, T, P, C \le 10^6$
Úttak
Prentaðu svarið á einni línu.
Dæmi
Inntak 1
1 1 1 1
Úttak 1
166374060
Inntak 2
2 7 1 8
Úttak 2
300941313
Inntak 3
20 26 2 14
Úttak 3
631490021
Athugasemd
- Í fyrsta dæminu er hér ein möguleg framvinda leiksins (athugaðu að þetta er ekki endilega besta stefnan):
- Ef þú framkvæmir Aðgerð B í $1$. umferð verða stigin þín $0$ og leiknum lýkur. Gerum ráð fyrir að þú framkvæmir Aðgerð A í staðinn og spilið sem snúið er við sýni einhyrning.
- Í þessari stöðu, ef þú framkvæmir Aðgerð B í $2$. umferð, verða stigin þín $2$ og leiknum lýkur. Gerum ráð fyrir að þú framkvæmir Aðgerð A í staðinn og spilið sem snúið er við sýni pöndu.
- Í þessari stöðu, ef þú framkvæmir Aðgerð B í $3$. umferð, verða stigin þín $2$ og leiknum lýkur. Gerum ráð fyrir að þú framkvæmir Aðgerð A í staðinn og spilið sem snúið er við sýni kött. Vegna þess að köttur var dreginn verða stigin þín $0$ og leiknum lýkur.
- Ef þú fylgir bestu stefnu má sýna að væntigildi stiganna er $\frac{7}{6}$.