wavedash.ppt

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

题目描述

Madeline 最近学会了新技巧——凌波微步：Wavedash！
但是她对这个技巧应用的仍然不是很熟练，因此她决定在一张**有向无环图** $G=(V,E)$ 上进行练习。图中的每个点上都有经验值 $w_i$ 。
具体来说，在一次练习中，Madeline 可以选择一条简单路径，即一条 $v_1\rightarrow v_2\rightarrow...\rightarrow v_k(k\ge 1)$ 的路径，其中 $v$ 两两不同且 $\forall i\in [1,k)$ ，都有 $(v_i,v_{i+1})\in E$ 。Madeline 会使用凌波微步沿着这条路径从 $v_1$ 跳到 $v_k$ ，并获得这条路径上所有点的经验值的乘积这么多的熟练度，即获得 $\prod_{i=1}^kw_{v_i}$ 的熟练度。
为了方便，Madeline 用 $V(P)$ 指代这条路径经过的点的集合，用 $W(P)$ 指代在这条路径上进行练习可以获得的熟练度。那么对于集合 $S\subseteq\{1,2,\cdots,n\}$ ，Madeline 认为这个集合的练习价值是
$f(S)=\left(\sum_{V(P)\subseteq S}W(P)\right)^2$
现在她想要知道，如果她等概率随机地选取一个（可空）集合 $S\subseteq\{1,2,\cdots,n\}$ ，该集合的练习价值的期望乘上 $2^n$ 后（即所有集合的练习价值之和）对 $998244353$ 取模的值是多少。

输入描述:

第一行两个正整数  表示有向图的点数与边数。
第二行  个正整数  表示每个点上的经验值。
接下来  行，每行两个正整数 ，表示一条有向边 。
对于  的数据，。保证图中无重边，且给出的图是一张有向无环图。

输出描述:

输出一行一个正整数表示答案。

示例1

输入

复制

输出

复制

说明

对于  的数据，。保证图中无重边，且给出的图是一张有向无环图。

备注:

以下用  代指 Madeline 走过一条简单路径  可获得的熟练度。以集合  与  为例：


以及 ，因此期望为 ，乘上  后为 。