$n$ 桶の絵の具が一列に並んでおり、各絵の具は $1$ 単位の体積を持ち、その色は $(r_i, g_i, b_i)$ で表されます。これから $n - 1$ 回の調色を行います。毎回、現在一列に並んでいる絵の具の桶から隣接する $2$ つを等確率で選び、それらを混ぜ合わせ、その後 $1$ 単位の体積を捨てます。このとき、色がそれぞれ $(r, g, b)$ と $(r', g', b')$ である $2$ つの絵の具を混ぜると、その色は $(\frac{r + r'}2, \frac{g + g'}2, \frac{b + b'}2)$ に変化します。
このようにランダムに絵の具の桶を繰り返し統合していったとき、最終的に得られる絵の具の $r, g, b$ の各色の値の期待値はいくらになるでしょうか。
入力
1行目に、絵の具の数を示す正の整数 $n$ が与えられます。
続く $n$ 行のうち $i$ 行目には、第 $i$ の絵の具の色を表す $3$ つの整数 $r_i, g_i, b_i$ が与えられます。
出力
期待される $r, g, b$ の値を $998244353$ を法とする剰余で、1行に空白区切りで出力してください。
すなわち、答えの各値が既約分数 $\frac ab$ で表されるとき、 $bx \equiv a \pmod {998244353}$ かつ $0\le x < 998244353$ を満たす整数 $x$ を出力してください。このような整数 $x$ は一意に存在することが証明できます。
入出力例
入力 1
3 62 12 0 12 303 0 42 192 0
出力 1
42 748683417 0
注記
最初に最初の $2$ つを混ぜた場合、最終的な結果は $\frac{\frac{x_1 + x_2}2 + x_3}2$ となり、そうでない場合は $\frac{x_1 + \frac{x_2 + x_3}2}2$ となります。したがって、結果は $\frac 38 x_1 + \frac 14 x_2 + \frac 38 x_3$ となります。
これより、$r$ の期待値は $\frac 38 \times 62 + \frac 14 \times 12 + \frac 38 \times 42 = 42$ となり、$g$ の期待値は $\frac{609}4$ となります。これが $998244353$ を法として $748683417$ になることは容易に確認できます。
入力 2
10 181 37 150 226 168 61 126 166 129 193 56 72 202 48 192 10 14 172 83 16 95 123 246 225 211 135 239 234 2 223
出力 2
837029038 403008335 287595555
制約
すべてのデータにおいて、$1\le n \le 10^5, 0\le r_i, g_i, b_i \le 255$ を満たします。
| テストケース | $n$ |
|---|---|
| $1$ | $=1$ |
| $2,3,4$ | $=2$ |
| $5,6$ | $=3$ |
| $7,8,9$ | $\le10$ |
| $10,11,12,13$ | $\le200$ |
| $14,15,16,17$ | $\le10^3$ |
| $18,19,20$ | $\le10^5$ |
ストーリー
蘭はいつの間にか少女へと成長していた。彼女の赤い瞳は今や松明のように輝き、その性格そのままに、青春と情熱を放っている。
この頃の彼女は、アトリエでエネルギーを揮発させるように絵を描くのが好きだった。今日もまた、彼女は気ままに絵の具を調合し始めた。
彼女は $n$ 桶の絵の具を目の前に一列に並べた。各絵の具は $1$ 単位の体積を持ち、その色は $(r_i, g_i, b_i)$ で表される。これから彼女は $n - 1$ 回の気ままな調色を行う。毎回、現在一列に並んでいる絵の具の桶から隣接する $2$ つを等確率で選び、それらを混ぜ合わせ、その後 $1$ 単位の体積を捨ててしまう。このとき、色がそれぞれ $(r, g, b)$ と $(r', g', b')$ である $2$ つの絵の具を混ぜると、その色は $(\frac{r + r'}2, \frac{g + g'}2, \frac{b + b'}2)$ に変化する。
「そんなの、もったいないよ。」
「まあ……これこそがアートってものよ！」
「はあ、わかったよ……」
「ねえ、教えて。ありとあらゆる世界の中で、私が調合する色の……期待値ってどんなものになるのかしら？」
「最終的に得られる色の $r, g, b$ それぞれの期待値のことかい？」——「はっ！あなたに聞く前に、もう計算しちゃったわよ！」
「ふん！私だって、今計算し終わったところよ！」
話している間に、蘭は絵の具を混ぜ終えていた。彼女は筆を手に取り、キャンバスに気ままに一筆描いた。
「ちょっと、まだ色が均一に混ざりきってないよ——」「言われなくてもわかってるわよ、狙った効果なんだから！」
無数の鮮やかな色彩はまだ融合しきっておらず、そのままキャンバスに残されていた。細い筋が静かにキャンバスの上で絡み合い、溶け合っている。そして筆致の末端では、様々な色が互いに交差し、滲み合っている。まるで——
それは彼女の瞳に映る流星のようだった。
彼女は振り返って私にピースサインを向けた。「なかなかいい感じでしょ？」その笑顔は、子供の頃と変わらず輝いていた。