This is the hard version of "Binary Stack", the only difference between the easy and hard versions are the constraints.

You have a binary array $a$ and a binary stack $s$, we define the operation $X(a,s)$ as the following: For each element of $a$ from left to right if it's equal to the top of the stack $s$, pop that top element from the stack, otherwise do nothing. For example if $a=110$ and $s=100$, then $X(a,s)$ will go as follow:

• $a:\underline{1}10$ $s:\underline{1}00$ first element of $a$ is equal to the top of $s$, so we remove the $1$ from top of $s$.
• $a:1\underline{1}0$ $s:\underline{0}0$ second element of $a$ is not equal to the top of $s$, so we don't remove the top element of $s$.
• $a:11\underline{0}$ $s:\underline{0}0$ third element of $a$ is equal to the top of $s$, so we remove the top element of $s$.
• At the end of the operation $s=0$.

You're give $a$ and $s$, if $a$ was shuffled randomly, what is the probability that at the end of the operation $X(a,s)$ s will be empty module $M=998244353$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1}\mod{M}$. In other words, output such an integer $x$ that $0 \le x < M$ and $x \cdot q \equiv p \pmod{M}$.

The first line contains 2 integers $|a|$ and $|s|$($1 \le |s| \le |a| \le 2 \cdot 10^5$), the length of $a$ and the length of $s$.

The second line contains $a$.

The third line contains $s$, where the leftmost element is the top of the stack $s$.

Print a single integer, the probability as stated above.

For the first example, there are 3 different arrays that can result from shuffling $a$: $011$, $101$ and $110$, only the first 2 will result in an empty stack, so the answer is $\frac{2}{3}$.