Reading KakaoTalk

There are $N$ people and $M$ messages in a chat room. The messages are numbered $1,2,\cdots,M$ from oldest to newest.

Message $i$ was written by person $A_i$, and exactly $B_i$ people have read message $i$.

For each person $p$, let $C_p$ be the index of the last message read by that person. If $C_p=0$, the person has read no messages. If $C_p=c$, the person has read every message $1,2,\cdots,c$ and has not read messages $c+1,c+2,\cdots,M$.

A person is considered to have read every message up to each message they wrote. Therefore, $C_{A_i}\ge i$ must hold for every $i$.

A sequence $C=(C_1,C_2,\cdots,C_N)$ is valid if all of the following conditions hold.

• $0\le C_p\le M$ ($1\le p\le N$).
• $C_{A_i}\ge i$ ($1\le i\le M$).
• Exactly $B_i$ people $p$ satisfy $C_p\ge i$ ($1\le i\le M$).

The input sequence $B$ satisfies $B_1\ge B_2\ge\cdots\ge B_M$. It is also guaranteed that at least one valid sequence $C$ exists.

Find the number of valid sequences $C$ modulo $998\,244\,353$.

The input is given from Standard Input in the following format:

$N\ M$ $A_1\ A_2\ \cdots\ A_M$ $B_1\ B_2\ \cdots\ B_M$

Print the number of valid sequences $C$ modulo $998\,244\,353$.

• $1\le N\le 200\,000$.
• $1\le M\le 200\,000$.
• $1\le A_i\le N$ ($1\le i\le M$).
• $0\le B_i\le N$ ($1\le i\le M$).
• $B_i\ge B_{i+1}$ ($1\le i<M$).
• At least one valid sequence $C$ exists.