Имеется $n$ банок с краской, выстроенных в ряд. Каждая банка содержит $1$ единицу объема краски, цвет которой задается тройкой $(r_i, g_i, b_i)$. Далее выполняется $n - 1$ операция смешивания: каждый раз равновероятно выбираются две соседние банки в текущем ряду, их содержимое смешивается, а затем $1$ единица объема выливается. Таким образом, при смешивании двух порций краски с цветами $(r, g, b)$ и $(r', g', b')$ результирующий цвет становится равным $(\frac{r + r'}2, \frac{g + g'}2, \frac{b + b'}2)$.
Если продолжать случайным образом объединять банки с краской до тех пор, пока не останется одна банка, каково будет математическое ожидание значений $r, g, b$ итоговой краски?
Входные данные
В первой строке вводится целое положительное число $n$, количество банок с краской.
В следующих $n$ строках содержатся по три целых числа $r_i, g_i, b_i$, задающих цвет $i$-й банки.
Выходные данные
Выведите в одну строку три целых числа — математические ожидания значений $r, g, b$ по модулю $998244353$.
Это означает, что если результат представляет собой несократимую дробь $\frac ab$, где $a$ и $b$ взаимно просты, необходимо вывести такое целое число $x$, что $bx \equiv a \pmod {998244353}$ и $0\le x < 998244353$. Можно доказать, что такое число $x$ единственно.
Примеры
Входные данные 1
3 62 12 0 12 303 0 42 192 0
Выходные данные 1
42 748683417 0
Примечание
Если сначала объединить первые две банки, то итоговый результат будет $\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
Ограничения
Для $100\%$ данных: $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$ произвольных смешиваний: каждый раз равновероятно выбираются две соседние банки в текущем ряду, их содержимое смешивается, а затем $1$ единица объема выливается. Таким образом, при смешивании двух порций краски с цветами $(r, g, b)$ и $(r', g', b')$ результирующий цвет становится равным $(\frac{r + r'}2, \frac{g + g'}2, \frac{b + b'}2)$.
— Это так расточительно.
— Ну... это же и называется искусством, разве нет!
— Ха, ладно, ладно...
— Эй, скажи, во всех возможных мирах, какой цвет я ожидаю получить... как он выглядит?
— Ты имеешь в виду математическое ожидание каждого из трех значений $r, g, b$ итогового цвета? — Ха! Я всё посчитала еще до того, как спросить тебя!
— Хм! Я, я тоже только что посчитал!
Пока мы разговаривали, Лан уже закончила смешивать цвета, взяла кисть, обмакнула её в краску и небрежно провела по холсту.
— Эй, цвета еще не смешались равномерно...
— Будто я не знаю, именно такой эффект мне и нужен!
Бесчисленные яркие цвета, еще не успевшие слиться воедино, были разом оставлены на холсте. Тонкие нити красок тихо переплетались и сливались на полотне. А на конце мазка различные цвета пересекались и размывались, словно...
Словно падающие звезды в её глазах.
Она повернулась ко мне и показала пальцами знак «V»: «Выглядит неплохо, правда?» Её улыбка была такой же лучезарной, как в детстве.