카톡 읽기

$N$명이 참여한 채팅방에 $M$개의 메시지가 있다. 메시지는 오래된 순서대로 $1,2,\cdots,M$번이다.

$i$번 메시지의 작성자는 $A_i$이고, 현재 $i$번 메시지를 읽은 사람은 정확히 $B_i$명이다.

각 사람 $p$에 대해 마지막으로 읽은 메시지의 번호를 $C_p$라고 하자. $C_p=0$이면 메시지를 하나도 읽지 않은 것이다. $C_p=c$이면 $p$는 $1,2,\cdots,c$번 메시지를 모두 읽었고, $c+1,c+2,\cdots,M$번 메시지는 읽지 않았다.

메시지를 작성한 사람은 자신이 작성한 메시지까지 읽은 것으로 간주한다. 따라서 모든 $i$에 대해 $C_{A_i}\ge i$여야 한다.

수열 $C=(C_1,C_2,\cdots,C_N)$가 다음 조건을 모두 만족하면 유효하다.

• $0\le C_p\le M$ ($1\le p\le N$).
• $C_{A_i}\ge i$ ($1\le i\le M$).
• $C_p\ge i$를 만족하는 사람 $p$의 수가 정확히 $B_i$이다 ($1\le i\le M$).

입력으로 주어지는 수열 $B$는 $B_1\ge B_2\ge\cdots\ge B_M$을 만족한다. 또한 유효한 수열 $C$가 하나 이상 존재함이 보장된다.

유효한 수열 $C$의 개수를 $998\,244\,353$으로 나눈 나머지를 구하여라.

입력은 다음과 같은 형식으로 주어진다.

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

유효한 수열 $C$의 개수를 $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$).
• 유효한 수열 $C$가 하나 이상 존재한다.