ACM-ICPC-OJ训练营

问题 1831 --Wavel Sequence

1831: Wavel Sequence

时间限制: 4 Sec 内存限制: 128 MB
提交: 13 解决: 12
[提交][状态][讨论版][命题人:]

题目描述

Have you ever seen the wave? It's a wonderful view of nature. Little Q is attracted to such wonderful thing, he even likes everything that looks like wave. Formally, he defines a sequence

a1,a2,...,an as ''wavel'' if and only if

a1<a2>a3<a4>a5<a6...

Picture from Wikimedia Commons

Now given two sequences

a1,a2,...,an and

b1,b2,...,bm, Little Q wants to find two sequences

f1,f2,...,fk(1≤fi≤n,fi<fi+1) and

g1,g2,...,gk(1≤gi≤m,gi<gi+1), where

afi=bgi always holds and sequence

af1,af2,...,afk is ''wavel''.

Moreover, Little Q is wondering how many such two sequences

f and

g he can find. Please write a program to help him figure out the answer.

输入描述

The first line of the input contains an integer

T(1≤T≤15), denoting the number of test cases.

In each test case, there are

2 integers

n,m(1≤n,m≤2000) in the first line, denoting the length of

a and

b.

In the next line, there are

n integers

a1,a2,...,an(1≤ai≤2000), denoting the sequence

a.

Then in the next line, there are

m integers

b1,b2,...,bm(1≤bi≤2000), denoting the sequence

输出描述

For each test case, print a single line containing an integer, denoting the answer. Since the answer may be very large, please print the answer modulo

998244353.

样例输入

样例输出

提示

(1)f=(1),g=(2).
(2)f=(1),g=(3).
(3)f=(2),g=(4).
(4)f=(3),g=(5).
(5)f=(1,2),g=(2,4).
(6)f=(1,2),g=(3,4).
(7)f=(1,3),g=(2,5).
(8)f=(1,3),g=(3,5).
(9)f=(1,2,3),g=(2,4,5).
(10)f=(1,2,3),g=(3,4,5).

来源

[提交][状态]