题目描述

有 n 个人玩石头剪刀布，分别编号为 1, 2, · · · , n ，每个人在决定好要出什么手势后，整局游戏都只会出这种手势。 游戏进行 n − 1 轮，第 1 轮由 1, 2 两人进行比赛，第 i (2 ≤ i ≤ n − 1) 轮由 i − 1 轮 的获胜者与第 i + 1 个人进行比赛，胜利者根据如下规则判断：

• 如果两人中一人出石头，一人出剪刀，则手势为石头的人获胜。

• 如果两人中一人出石头，一人出布，则手势为布的人获胜。

• 如果两人中一人出布，一人出剪刀，则手势为剪刀的人获胜。

• 否则如果两人手势一样，编号小的获胜。

你知道每个人可能决定要出的手势集合，并且每个人都会等概率地从自己的集合中 选择一个手势，现在请你求出所有可能中每个人的获胜概率。 答案对 $998, 244, 353$ 取模。

输入格式

第一行一个整数 n 表示人数。

接下来 n 行，第 i 行输入一个长度为 3 的仅包含 01 的字符串 $s_i$

若 $s_{i,1} = 1$ 则第 i 个人的手势集合包含石头。

若 $s_{i,2} = 1$ 则第 i 个人的手势集合包含剪刀。

若 $s_{i,3} = 1$ 则第 i 个人的手势集合包含布。

保证 $s_{i,1}, s_{i,2}, s_{i,3}$ 不全为 0。

输出格式

一行输出 n 个数，第 i 个数表示第 i 个人获胜的概率对 $998244353$ 取模的结果。

输入输出样例

样例 1 输入

4
101
011
110
101

【样例 1 输出】

748683265 811073537 811073537 623902721