Problem C
Cursed Cactus Challenge
You are given a simple connected graph $G$ with $n$ vertices and $m$ edges. Each vertex $i$ has a value $a_ i$. No two edges connect the same pair of vertices. Interestingly, each edge lies in at most one simple cycle.
A simple cycle is a sequence of $k$ distinct vertices $v_1,v_2,\dots ,v_ k$, such that there is an edge connecting $v_ i$ and $v_{i+1}$ for every $1 \leq i \leq k-1$, and also an edge connecting $v_ k$ and $v_1$. We note that these $k$ edges lies in the simple cycle $v_1 \to v_2 \to \dots \to v_ k \to 1$.
Let $S$ be a subset of vertices. We call $S$ an independent set if for all $u,v \in S$ and $u \neq v$, there is no edge connecting the vertices $u$ and $v$. The score $F(S)$ of an independent set $S$ is defined as
\[ F(S) = \left(\sum _{v \in S} a_ v\right)^2 \]Let $\mathcal{I}$ be the set of all possible independent sets in $G$. In other words,
\[ \mathcal{I} = \{ S \subseteq \{ 1,2,\dots ,n\} \mid S \text { is an independent set}\} \]Find the following sum, modulo $998\, 244\, 353$.
\[ \sum _{S \in \mathcal{I}} F(S) \]Input
The first line of input contains two integers $n$ ($2 \leq n \leq 10^5$) and $m$ ($n-1 \leq m \leq 2n$).
The second line contains $n$ integers, the $i$-th of which denotes $a_ i$ ($1 \leq a_ i \leq 10^8$).
It is guaranteed that the given graph is simple, connected, and each edge lies in at most one simple cycle.
Output
Output $\sum _{S \in \mathcal{I}} F(S)$, modulo $998\, 244\, 353$.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 2 1 1 1 1 2 2 3 |
7 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 4 3 2 3 3 1 2 2 3 3 4 4 1 |
92 |
| Sample Input 3 | Sample Output 3 |
|---|---|
10 12 1 2 3 4 5 6 7 8 9 10 1 2 2 3 3 1 1 4 4 5 5 1 1 6 6 7 7 1 1 8 8 9 9 10 |
50520 |
