#P7476. [2017年杭电多校]Wavel Sequence

    ID: 7489 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF2000提高计数 DP线性 DP前缀和优化 DP滚动数组

[2017年杭电多校]Wavel Sequence

Wavel Sequence

Problem Description

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,...,ana_1,a_2,...,a_n as ''wavel'' if and only if a1<a2>a3<a4>a5<a6...a_1<a_2>a_3<a_4>a_5<a_6... Picture from Wikimedia Commons Now given two sequences a1,a2,...,ana_1,a_2,...,a_n and b1,b2,...,bmb_1,b_2,...,b_m, Little Q wants to find two sequences f1,f2,...,fk(1≤fi≤n,fi<fi+1)f_1,f_2,...,f_k(1\leq f_i\leq n,f_i<f_{i+1}) and g1,g2,...,gk(1≤gi≤m,gi<gi+1)g_1,g_2,...,g_k(1\leq g_i\leq m,g_i<g_{i+1}), where afi=bgia_{f_i}=b_{g_i} always holds and sequence af1,af2,...,afka_{f_1},a_{f_2},...,a_{f_k} is ''wavel''. Moreover, Little Q is wondering how many such two sequences ff and gg he can find. Please write a program to help him figure out the answer.

Input

The first line of the input contains an integer T(1≤T≤15)T(1\leq T\leq15), denoting the number of test cases. In each test case, there are 22 integers n,m(1≤n,m≤2000)n,m(1\leq n,m\leq 2000) in the first line, denoting the length of aa and bb. In the next line, there are nn integers a1,a2,...,an(1≤ai≤2000)a_1,a_2,...,a_n(1\leq a_i\leq 2000), denoting the sequence aa. Then in the next line, there are mm integers b1,b2,...,bm(1≤bi≤2000)b_1,b_2,...,b_m(1\leq b_i\leq 2000), denoting the sequence bb.

Output

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 998244353998244353.

Sample Input

1

3 5

1 5 3

4 1 1 5 3

Sample Output

10

Hint

(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).

Source

2017 Multi-University Training Contest - Team 4

https://acm.hdu.edu.cn/showproblem.php?pid=6078