你是 ICPC 王国的战略家。你收到情报称，王国附近的一条狭窄通道将遭受怪物袭击。这条狭窄通道可以表示为一个 2 行（编号为 1 到 2）和 $N$ 列（编号为 1 到 $N$）的网格。记 $(r, c)$ 为第 $r$ 行第 $c$ 列的单元格。每天都有一个战力为 $P_{r,c}$ 的士兵被分配去守卫 $(r, c)$。

已知通道内雾气弥漫。在一天之内，通道中的每一列都有 50% 的概率被雾覆盖。如果一列被雾覆盖，那么分配到该列的两个士兵当天就不会部署。否则，分配的士兵将会部署。

定义一个连通区域 $[u, v]$ ($u \le v$) 为从 $u$ 到 $v$（包含边界）的一组最大连续列，使得该集合中的每一列都没有被雾覆盖。下图展示了连通区域的一个例子。灰色单元格为被雾覆盖的区域。图中共有 4 个连通区域：$[1, 2]$、$[4, 6]$、$[9, 9]$ 和 $[11, 11]$。

连通区域

连通区域 $[u, v]$ 的强度计算如下：设 $m_1$ 和 $m_2$ 分别为连通区域第一行和第二行士兵的最大战力。形式化地，$m_r = \max(P_{r,u}, P_{r,u+1}, \dots, P_{r,v})$，其中 $r \in \{1, 2\}$。如果 $m_1 = m_2$，则强度为 0。否则，强度为 $\min(m_1, m_2)$。

部署的总强度是所有连通区域强度之和。请确定在任意一天部署的总强度的期望值。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 100\,000$)。 接下来的两行，每行包含 $N$ 个整数 $P_{r,c}$ ($1 \le P_{r,c} \le 200\,000$)。

输出格式

设 $M = 998\,244\,353$。可以证明期望总强度可以表示为一个不可约分数 $\frac{x}{y}$，其中 $x$ 和 $y$ 为整数且 $y \not\equiv 0 \pmod M$。输出一个整数 $k$，满足 $0 \le k < M$ 且 $k \cdot y \equiv x \pmod M$。

样例

输入 1

3
8 4 5
5 4 8

输出 1

249561092

说明 1

通道共有 8 种可能的场景，每种场景发生的概率相等。因此，期望总强度为 $(0 + 5 + 10 + 5 + 5 + 0 + 5 + 0)/8 = \frac{15}{4}$。由于 $249\,561\,092 \cdot 4 \equiv 15 \pmod{998\,244\,353}$，该样例的输出为 $249\,561\,092$。

输入 2

5
10 20 5 8 5
5 20 7 5 8

输出 2

811073541

说明 2

期望总强度为 $\frac{67}{16}$。