You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

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$ 的路径。