You are given two arrays $a_1, a_2, \dots , a_n$ and $b_1, b_2, \dots , b_m$. Array $b$ is sorted in ascending order ($b_i < b_{i + 1}$ for each $i$ from $1$ to $m - 1$).

You have to divide the array $a$ into $m$ consecutive subarrays so that, for each $i$ from $1$ to $m$, the minimum on the $i$-th subarray is equal to $b_i$. Note that each element belongs to exactly one subarray, and they are formed in such a way: the first several elements of $a$ compose the first subarray, the next several elements of $a$ compose the second subarray, and so on.

For example, if $a = [12, 10, 20, 20, 25, 30]$ and $b = [10, 20, 30]$ then there are two good partitions of array $a$:   $[12, 10, 20], [20, 25], [30]$;  $[12, 10], [20, 20, 25], [30]$. 

You have to calculate the number of ways to divide the array $a$. Since the number can be pretty large print it modulo 998244353.


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the length of arrays $a$ and $b$ respectively.

The second line contains $n$ integers $a_1, a_2, \dots , a_n$ ($1 \le a_i \le 10^9$) — the array $a$.

The third line contains $m$ integers $b_1, b_2, \dots , b_m$ ($1 \le b_i \le 10^9; b_i < b_{i+1}$) — the array $b$.


-----Output-----

In only line print one integer — the number of ways to divide the array $a$ modulo 998244353.


-----Examples-----
Input
6 3
12 10 20 20 25 30
10 20 30

Output
2

Input
4 2
1 3 3 7
3 7

Output
0

Input
8 2
1 2 2 2 2 2 2 2
1 2

Output
7

Difficulty: interview

Starter code:

Solutions:
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
mod=998244353
sol=1
i=n-1
j=m-1
while sol>0 and j>=0:
    goal=b[j]
    s=0
    r=False
    while i>=0 and a[i]>=goal:
        if r:
            s+=1
        else:
            if a[i]==goal:
                r=True
                s=1
        i-=1
    if j==0:
        s=min(s,1)
        if i>=0:
            s=0
    sol*=s
    sol%=mod
    j-=1
print(sol)

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))

MOD = 998244353

out = 1

first = -1
curr = m - 1

for i in range(n - 1, -1 ,-1):
    while a[i] < b[curr]:
        if first > -1:
            out *= (first - i)
            out %= MOD
        else:
            out = 0
        first = -1
        curr -= 1
        
        if curr < 0:
            out = 0
            break
    if a[i] == b[curr] and first == -1:
        first = i

if curr == 0 and first != -1:
    print(out)
else:
    print(0)


n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))

M=[a[i] for i in range(n)]
for i in range(n-2,-1,-1):
    M[i]=min(M[i],M[i+1])

res=1
mod=998244353
val=b[m-1]
id=n-1
count=m-1
l,r=-1,-1
while count and id>-1:
    if M[id]>val:
        id-=1
    elif M[id]==val:
        if r==-1:
            r=id
        id-=1
    elif val>M[id]:
        l=id+1
        res*=max((r-l+1),0)
        res%=mod
        count-=1
        r=-1
        l=-1
        val=b[count]

if count:
    res=0
    print(res)
else:
    check=min(a[i] for i in range(id+1))
    if check==b[0]:
        print(res)
    else:
        print(0)

MOD = 998244353
n, m = list(map(int, input().split()))
d = dict()
a = [0] + list(map(int, input().split()))
b = list(map(int, input().split()))
for i in range(m):
    d[b[i]] = i
c = [-1] * m
for i, x in enumerate(a):
    if x in d:
        c[d[x]] = i
idx = n
ans = 1
for i in range(m - 1, -1, -1):
    while b[i] <= a[idx]:
        idx -= 1
    if c[i] <= idx:
        print(0)
        return
    if i > 0:
        ans *= c[i] - idx
    elif idx > 0:
        print(0)
        return
    ans %= MOD
print(ans)


from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
    return int(input())

def rl():
    return list(map(int, input().split()))


def solve():
    n, m = rl()
    A = rl()
    B = rl()
    mod = 998244353
    if A[0] < B[0]:
        print(0)
        return

    # ptr = len(B) - 1
    # streak = 0
    # answer = 1
    # _min = A[-1]
    # for a in A[::-1]:
        # _min = min(_min, a)
        # if _min == B[ptr]:
            # streak += 1
        # elif _min < B[ptr]:
            # ptr -= 1
            # if _min < B[ptr]:
                # print (0)
                # return
    mins = dd(int)
    _min = A[-1]
    for a in A[::-1]:
        _min = min(_min, a)
        mins[_min] += 1

    if _min != B[0]:
        print(0)
        return

    answer = 1
    for b in B[1:]:
        if mins[b] == 0:
            print(0)
            return
        else:
            answer = (answer * mins[b]) % mod

    print (answer)






mode = 'S'

if mode == 'T':
    t = ri()
    for i in range(t):
        solve()
else:
    solve()


import sys
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
last=[]
i=n-1
j=m-1
MOD=998244353
failflag=0
while j>=0 and i>=0:
    r=b[j]
    while i>=0:
        if a[i]==r:
            last.append(i)
            break
        if a[i]<r:
            failflag=1
            break
        i-=1
    if i<0:
        break
    j-=1
last.reverse()
if len(last)!=m:
    print(0)
    return
for i in range(last[0]):
    if a[i]<b[0]:
        failflag=1
if failflag==1:
    print(0)
    return
ans=1
for i in range(1,m):
    for j in range(last[i],last[i-1]-1,-1):
        if a[j]<b[i]:
            break
    ans=((last[i]-j)*ans)%MOD
print(ans)

import sys
# import math
# from collections import deque
# import heapq
# from math import inf
# from math import gcd

# print(help(deque))
# 26
pprint = lambda s: print(' '.join(map(str, s)))
input = lambda: sys.stdin.readline().strip()
ipnut = input
# n,m = map(int, input().split())
# n = int(input())
#
n,m = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
mod = 998244353
suf_min = [(10000000000,-1)]
a_r = list(reversed(a))
for i in range(n):
    if a_r[i]<suf_min[-1][0]:
        suf_min.append((a_r[i],n-i-1))
    else:
        suf_min.append(suf_min[-1])
suf_min.reverse()

if suf_min[0][0]!=b[0]:
    print(0)
    return
ans = 1
def bin(a):
    l = 0
    r = n+1
    while r-l>1:
        m = (r+l)//2
        if suf_min[m][0]>a:
            r = m
        else:
            l = m
    return l
for k in range(m-1):
    j= bin(b[k+1])
    if suf_min[j][0]!=b[k+1]:
        print(0)
        return
    ans = (ans*(suf_min[j][1]-suf_min[bin(b[k+1]-1)][1]))%mod
print(ans)