D. 图上随机游走

题目描述

cyx 在随机游走。

给出一个有向无环图 $G$，cyx 要从 $1$ 号点，依次经过若干条边走到 $n$ 号点，走到 $n$ 号点即为结束。每当这个 cyx 站在某个点 $u$ 上，cyx 会以以下三种方式走一步：

• cyx 有 $a_u \%$ 的概率，直接回到 $1$ 号点。
• cyx 有 $b_u \%$ 的概率不动，浪费一步机会。
• 如果前两种事件均未发生，cyx 将从这个点的出边中均匀随机选择一条边走出。也就是说这种事件的发生概率为 $(100-a_u-b_u)\%$。

值得注意是，对于同一步，会直接决定发生哪种事件。

请你求出 cyx 期望使用多少步走到 $n$ 号点。可以证明答案是一个有理数，你只需要输出答案对 $998244853$ （一个质数）取模的值。

输入格式

第一行给定 $n,m$，表示有向无环图的点数和边数；

接下来一行给定 $n-1$ 个整数，表示 $a_1 \sim a_{n-1}$；

接下来一行给定 $n-1$ 个整数，表示 $b_1 \sim b_{n-1}$；

接下来 $m$ 行，每行给定两个整数 $u,v$，表示 $G$ 中的一条边 $u\to v$。

输出格式

一行一个整数，答案对 $998244853$ 取模的值。

样例 #1

样例输入 #1

4 5
25 25 25
25 25 25
1 2
1 3
2 3
2 4
3 4

样例输出 #1

181499070

数据范围

对于所有数据有 $1\le n \le 10^5$，$0 \le m \le 2\times 10^6$，$0\le a_u , b_u\le 99$ 且 $a_u + b_u \le 99$。保证图中无入边的点有且只有 $1$，无出边的点有且只有 $n$，并且存在至少一条 $1\sim n$ 的路径。