Hide

# Problem CCursed 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

Hide