33123번 - Narrower Passageway 다국어

문제

You are a strategist of The ICPC Kingdom. You received an intel that there will be monster attacks on a narrow passageway near the kingdom. The narrow passageway can be represented as a grid with 2ドル$ rows (numbered from 1ドル$ to 2ドル$) and $N$ columns (numbered from 1ドル$ to $N$). Denote $(r, c)$ as the cell in row $r$ and column $c$. A soldier with a power of $P_{r,c}$ is assigned to protect $(r, c)$ every single day.

It is known that the passageway is very foggy. Within a day, each column in the passageway has a 50ドル\%$ chance of being covered in fog. If a column is covered in fog, the two soldiers assigned to that column are not deployed that day. Otherwise, the assigned soldiers will be deployed.

Define a connected area $[u, v]$ ($u ≤ v$) as a maximal set of consecutive columns from $u$ to $v$ (inclusive) such that each column in the set is not covered in fog. The following illustration is an example of connected areas. The grayed cells are cells covered in fog. There are 4ドル$ connected areas: $[1, 2],ドル $[4, 6],ドル $[9, 9],ドル and $[11, 11]$.

The strength of a connected area $[u, v]$ can be calculated as follows. Let $m_1$ and $m_2$ be the maximum power of the soldiers in the first and second rows of the connected area, respectively. Formally, $m_r = \max(P_{r,u}, P_{r,u+1}, \dots , P_{r,v})$ for $r \in \{1, 2\}$. If $m_1 = m_2,ドル then the strength is 0ドル$. Otherwise, the strength is $\min(m_1, m_2)$.

The total strength of the deployment is the sum of the strengths for all connected areas. Determine the expected total strength of the deployment on any single day.

입력

The first line consists of an integer $N$ (1ドル ≤ N ≤ 100,円 000$).

Each of the next two lines consists of $N$ integers $P_{r,c}$ (1ドル ≤ P_{r,c} ≤ 200,円 000$).

출력

Let $M = 998,円 244,円 353$. It can be shown that the expected total strength can be expressed as an irreducible fraction $\frac{x}{y}$ such that $x$ and $y$ are integers and $y \not\equiv 0 \pmod M$. Output an integer $k$ in a single line such that 0ドル ≤ k < M$ and $k \cdot y \equiv x \pmod M$.

제한

힌트