Defend Ponyville

题号：NC223728
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Changelings are going to attack Ponyville again! Their goal is to absorb the love inside all the ponies as their food! Unluckily, the defense of Ponyville is now too fragile to fight against them. Twilight Sparkle must reinforce the defense magic cast around Ponyville before Changelings' final attack.

There are $n$ magic sources in Ponyville, together with $m$ undirected connections. Each connection connects exactly $2$ different magic sources, and there is at most $1$ connection between $2$ magic sources. The defense power is initially $0$ . At any time, Twilight Sparkle can cast a spell to a set of $n-1$ connections (the set cannot be empty) that connects all the $n$ sources (any source can reach other sources through these $n-1$ connections), and the defense power will increase by $1$ . However, the same set of connections can be used only once every day to increase the defense power. The two sets are the same if and only if they have precisely the same connections. Twilight Sparkle only has $t$ days to prepare before Changelings pour in, so every day she will gain as much defense power as possible.

But due to the unstable magic field, some connections may disappear in some days. Luckily, thanks to Twilight's research, we know that the probability for the $j$ -th connection to exist on the $i$ -th day $(i=1,2,\ldots ,t)$ is $q_j+(p_j-q_j)a^{-(i-1)}\ (0\le p_j, q_j\le 1,p_j\ne q_j)$ , where $a$ is a given constant. Twilight Sparkle wants to know the expectation of total defense power she can gain in $t$ days. Can you help her and protect Ponyville?

输入描述:

The first line contains  integers  .

The following  lines are the  connections. The -th line contains  integers , indicating that the -th connection is between  and ,  (  and  ).

It's guaranteed that all the data are picked randomly.

输出描述:

One integer indicating the expectation of the total defense power Twilight Sparkle can get. You should output the answer modulo $998244353$ . Formally, let $M=998244353$ . It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$ , where $p$ and $q$ are integers and $q\not\equiv 0\mod M$ . Output the integer equal to $p \times q^{-1}\mod M$ . In other words, output such an integer $x$ that $0 \le x < M$ and $x \cdot q \equiv p \mod M$ .

示例1

输入

复制

3 3 2 2
1 2 1 1 0 1
2 3 1 1 0 1
1 3 1 1 0 1

输出

复制

249561092

示例2

输入

复制

3 2 100 2
1 2 1 1 0 1
1 3 1 1 0 1

输出

复制

示例3

输入

复制

6 6 2 2
6 2 1 2 3 4
2 3 4 5 6 7
6 3 1 4 6 7
5 1 1 3 2 5
4 1 1 4 7 8
4 5 3 5 4 7

输出

复制