芒砀山的神秘数字
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

巫山老伯所在地芒砀山有神秘数字的出现,世人惊讶。此神秘数字一旦破解,秦皇便可以此长生不老,构建万世天宫。
神秘数字是在一个陨石坠落之时,所产生的。陨石坠落时分为两块,分别落在了芒砀山的南北两侧。导致芒砀山南北两侧皆有一串神秘数字。
现秦始皇派巫山老伯前去解开此神秘数字背后的秘密。
神秘数字南北方的长度分别为n和m。
巫山老伯发现,此两串神秘数字的背后隐藏的秘密是一个数。
巫山老伯发现神秘数字背后的数字就是南方神秘数字串的子序列的值大于北方神秘数字串的值的序列个数。

输入描述:

输入T (T<= 10)
输入n m 表示南方神秘数字串的长度和北方神秘数字串的长度。(1<= m <= n <= 3000 )
输入南方神秘数字串
输入北方神秘数字串

输出描述:

输出两串神秘数字的背后隐藏的秘密是一个数,并将此数对998244353取模。
示例1

输入

复制
3
4 2
1234
13
4 2
1034
13
4 1
1111
2

输出

复制
9
6
11

说明

第一组样例解释:
比北方神秘数字串大的南方神秘数字串的子序列串有:
14  124 1234 34 23 123 234 134 24