Amplitude recently implemented journeys! This problem is inspired by journeys, but knowledge of how journeys works or what the product surfaces is not required to solve this problem.

Spenser is on a journey as CEO of Amplitude and is charting the future direction of the company. The company can be in one of $N$ different states, and depending on Amplitude's current state, he can take certain actions to move Amplitude to a different state. Spenser's actions can never result in Amplitude returning to a previous state.

Spenser wants to know, for each possible pair of starting and ending state, how many distinct journeys there are that Amplitude can take to get between the starting state and ending state. Formally, we say that a sequence of states $(s_1,\dots ,s_K)$ is a journey between state $s_1$ and state $s_K$ if and only if for every $i$ where $1\le i<K$, there is an action that Spenser can take to move Amplitude directly from state $s_i$ to state $s_{i+1}$.

Two journeys are different if some state appears in one journey but not in the other.

Constraints

$1\le N\le 500$

If Spenser can take a single action to make Amplitude go from state $i$ to state $j$, then $i<j$.

Subtask 1 [1 point]

$1\le N\le 10$

Subtask 2 [1 point]

$1\le N\le 50$

Subtask 3 [1 point]

No additional constraints.

Input Specification

The first line of input contains a single positive integer, $N$.

The next $N$ lines each contain a binary string of length $N$. If the $j$th character of line $i$ is a 1, then Spenser can move Amplitude directly from state $i$ to state $j$. Otherwise, the $j$th character of line $i$ is a 0.

Output Specification

Output $N$ lines, each with $N$ integers. Let $f(i,j)$ be the number of journeys with starting state $i$ and ending state $j$. The $j$th integer on the $i$th line should be the remainder when $f(i,j)$ is divided by 998244353.

Sample Input 1

3
011
001
000

Sample Output 1

1 1 2
0 1 1
0 0 1

Sample Explanation 1

There are two journeys from state 1 to state 3: $(1,2,3)$ and $(1,3)$.

There is one journey from state 1 to state 2: $(1,2)$.

There is one journey from state 2 to state 3: $(2,3)$.

There is always exactly one journey from a state to itself.

Sample Input 2

3
010
001
000

Sample Output 2

1 1 1
0 1 1
0 0 1

Sample Explanation 2

There is now only one journey from state 1 to state 3: $(1,2,3)$.