Ambiguous Relationship Investigation

There are \(n\) boys and \(n\) girls, numbered from \(1\) to \(n\). There are \(m\) pairs of ambiguous relationships, each between a boy and a girl. Teacher An Yuan wants to find a group of boys and girls such that every boy and every girl in the group has an ambiguous relationship with every girl and every boy in the group. In other words, if the group contains \(s\) boys and \(t\) girls then every one of the \(s\t t\) possible edges between them must exist in the input.

Among all such groups, the teacher chooses one with the maximum total number of students (i.e. maximum \(s+t\)). If there are several groups with the same total, he chooses the one with the most boys. (Note that one side of the group may be empty.)

After selecting the group, the teacher will pick exactly \(k\) ambiguous relationships from all the relationships among the group (which form the complete bipartite graph \(K_{s,t}\)) so that every student in the group appears in at least one of the chosen relationships. Compute the total number of schemes modulo \(19921228\).

The number of valid selections (if \(s\) and \(t\) are the counts of boys and girls in the chosen group) can be computed by using the principle of inclusion-exclusion as follows:

[ \sum_{i=0}^{s}\sum_{j=0}^{t} (-1)^{i+j} \binom{s}{i} \binom{t}{j} \binom{(s-i)(t-j)}{k}, ]

Output \(0\) if no valid selection exists.

inputFormat

The first line contains three integers \(n\), \(m\), and \(k\) (with \(0\le n\le\text{small}\), \(0\le m\le n^2\), and \(0\le k \le n^2\)).

Then \(m\) lines follow, each containing two integers \(a\) and \(b\) (1-indexed), indicating there is an ambiguous relationship between boy \(a\) and girl \(b\).

outputFormat

Output a single integer, the number of valid ways to choose the \(k\) relationships from the group modulo \(19921228\).

sample

3 4 2
1 1
1 2
2 1
2 2
3 1

0