题目描述

给出一张 (n) 个点 (m) 条边的无向连通图，其中每条边至多属于一个简单环，保证没有自环，可能有重边。你需要为其中每条边定向，其中第 (i) 个点的出度不能超过 (a_i)，求方案数。

输入格式

第一行包括两个正整数 (n, m)。

接下来 (m) 行，每行两个正整数，表示有一条边连接这两个点。

最后一行 (n) 个正整数，其中第 (i) 个表示 (a_i)。

输出格式

输出一个非负整数，表示答案对 (998244353) 取模后的结果。

样例

输

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

输出

7

数据范围与提示

对于全部数据，(1 \leq a_i \leq n \leq 10^5)，(1 \leq m \leq 2×10^5)。