Pak Chanek has a directed acyclic graph (a directed graph that does not have any cycles) containing \(N\) vertices. Vertex \(i\) has \(S_i\) edges directed away from that vertex. The \(j\)-th edge of vertex \(i\) that is directed away from it, is directed towards vertex \(L_{i,j}\) and has an integer \(W_{i,j}\) (\(0\leq W_{i,j}\leq1\)). Another information about the graph is that the graph is shaped in such a way such that each vertex can be reached from vertex \(1\) via zero or more directed edges.
Pak Chanek has an array \(Z\) that is initially empty.
Pak Chanek defines the function dfs as follows:
// dfs from vertex i
void dfs(int i) {
// iterate each edge of vertex i that is directed away from it
for(int j = 1; j <= S[i]; j++) {
Z.push_back(W[i][j]); // add the integer in the edge to the end of Z
dfs(L[i][j]); // recurse to the next vertex
}
}
Note that the function does not keep track of which vertices have been visited, so each vertex can be processed more than once.
Let's say Pak Chanek does dfs(1) once. After that, Pak Chanek will get an array \(Z\) containing some elements \(0\) or \(1\). Define an inversion in array \(Z\) as a pair of indices \((x, y)\) (\(x < y\)) such that \(Z_x > Z_y\). How many different inversions in \(Z\) are there if Pak Chanek does dfs(1) once? Since the answer can be very big, output the answer modulo \(998\,244\,353\).
Output
An integer representing the number of inversions in \(Z\) if Pak Chanek does dfs(1) once. Since the answer can be very big, output the answer modulo \(998\,244\,353\).
Note
The following is the dfs(1) process on the graph.
In the end, \(Z=[0,1,0,1,1,0]\). All of its inversions are \((2,3)\), \((2,6)\), \((4,6)\), and \((5,6)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2
4 0
3 1
0
1
2 0
2
3 1
5 1
0
|
4
|