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 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 is a journey between state and state if and only if for every where , there is an action that Spenser can take to move Amplitude directly from state to state .
Two journeys are different if some state appears in one journey but not in the other.
Constraints
If Spenser can take a single action to make Amplitude go from state to state , then .
Subtask 1 [1 point]
Subtask 2 [1 point]
Subtask 3 [1 point]
No additional constraints.
Input Specification
The first line of input contains a single positive integer, .
The next lines each contain a binary string of length . If the th character of line
is a 1
, then Spenser can move Amplitude directly from state to state . Otherwise, the th character
of line is a 0
.
Output Specification
Output lines, each with integers. Let be the number of journeys with starting state and
ending state . The th integer on the th line should be the remainder when 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: and .
There is one journey from state 1 to state 2: .
There is one journey from state 2 to state 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: .
Comments