Wormhole Construction

E‐country has \(n\) cities, numbered from \(1\) to \(n\). In order to make travel between the cities more convenient, the transportation ministry plans to build some wormholes. Each wormhole is a directed passage from one city to another; self–loops and multiple wormholes between two cities are allowed. Each wormhole is assigned a positive integer label.

A construction plan is called good if the following conditions are satisfied. Let \(d\) be a nonnegative integer such that:

1. Every city is the origin of exactly \(d\) wormholes and the destination of exactly \(d\) wormholes.
2. For every city, among the wormholes leaving it the labels \(1, 2, \dots, d\) appear exactly once.
3. For every city, among the wormholes arriving at it the labels \(1, 2, \dots, d\) appear exactly once.
4. For any city \(u\) and any two integers \(1 \le j_1, j_2 \le d\), if by first taking the wormhole with label \(j_1\) from \(u\) and then the wormhole with label \(j_2\) you reach \(v_1\), and by taking first the wormhole with label \(j_2\) and then \(j_1\) you reach \(v_2\), then it is necessary that \(v_1 = v_2\). In other words, if we define functions \(f_1, f_2, \dots, f_d\) where \(f_j(u)\) is the destination of the wormhole leaving city \(u\) with label \(j\), then we have \[ f_{j_1}\bigl(f_{j_2}(u)\bigr) = f_{j_2}\bigl(f_{j_1}(u)\bigr) \quad \text{for all } u \text{ and all } 1 \le j_1,j_2 \le d. \]

In particular, the plan with \(d=0\) (i.e. no wormholes built) is considered good.

Initially, engineers have built \(m\,n\) wormholes with labels \(1,2,\dots,m\); this initial plan is good, so each of the functions \(f_1,\dots,f_m\) is a permutation of \(\{1,2,\dots,n\}\) and they commute pairwise. Now they want to construct an additional \(k\,n\) wormholes with labels \(m+1, m+2, \dots, m+k\) such that the entire plan (with \(m+k\) wormholes per city) remains good. In other words, if we extend the functions to \(f_{m+1},\dots,f_{m+k}\) (each of which must be a permutation of \(\{1,2,\dots,n\}\)) the condition \[ f_{j_1} \circ f_{j_2} = f_{j_2} \circ f_{j_1} \quad \text{for all } 1 \le j_1,j_2 \le m+k \] must continue to hold.

Your task is to compute the number of ways to choose the new \(k\,n\) wormholes (that is, choose the permutations \(f_{m+1},\dots,f_{m+k}\)) so that the entire plan is good. Since the answer can be very large, output it modulo \(998244353\).

Hint: For each city \(u\) and each label \(j\) (\(1 \le j \le m+k\)), the wormhole with that label gives a permutation \(f_j: \{1,2,\dots,n\} \to \{1,2,\dots,n\}\). The conditions imply that the first \(m\) permutations commute and form an abelian group that partitions the cities into orbits. On each orbit, any permutation commuting with the group is uniquely determined by its value on one city, and there are as many choices as the size of the orbit. Thus, if the orbits have sizes \(r_1, r_2, \dots, r_t\), the number of ways to extend the plan is \[ \Bigl( \prod_{i=1}^t r_i \Bigr)^k \pmod{998244353}. \]

inputFormat

The input begins with a line containing three integers \(n\), \(m\) and \(k\) (\(1 \le n \le 10^5\), \(0 \le m \le n\), \(0 \le k \le 10^5\)). Here, \(n\) is the number of cities, \(m\) is the number of wormhole labels already built, and \(k\) is the number of new wormhole labels to be added.

If \(m \ge 1\), then the next \(m\) lines follow. The \(j\)-th of these lines contains \(n\) space–separated integers. The \(i\)-th integer on that line is \(f_j(i)\), representing the destination city of the wormhole leaving city \(i\) with label \(j\). When \(m = 0\), no such lines appear.

outputFormat

Output a single integer: the number of ways to choose the new \(k\,n\) wormholes so that the overall construction plan is good, modulo \(998244353\).

sample

2 1 1
1 2

1