Sakurada Reset
Time Limit: 15000/12000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
咲良田即将迎来重大的变革。为了阻止这一变革，浅井惠会进行一系列的行动。让我们用一个数字序列$a$表示浅井惠可以采取的行动，其中第$i$个数字$a_i$表示浅井惠可以采取的第$i$个行动。浅井惠可以选择$a$的一个子序列作为自己的实际行动序列。同时，变革的发起者也会从数字序列$b$中选择一个子序列作为自己的实际行动序列。
两个行动序列$x,y$不同当且仅当它们的长度不同或存在一个位置$p$满足$x_p \neq y_p$。行动序列$x$的影响度$=\sum_{i=1}^{l} 1000^{l-i} \cdot x_i$，其中$l$是$x$的长度。
浅井惠能阻止变革当且仅当浅井惠的行动序列的影响度大于变革者的行动序列的影响度。双方各选取一个行动序列，问有多少种选取方案使得浅井惠可以阻止变革。两种选取方案不同当且仅当存在至少一方在两个方案中选择了不同的行动序列。答案对$998244353$取模。
两个行动序列$x,y$不同当且仅当它们的长度不同或存在一个位置$p$满足$x_p \neq y_p$。行动序列$x$的影响度$=\sum_{i=1}^{l} 1000^{l-i} \cdot x_i$，其中$l$是$x$的长度。
浅井惠能阻止变革当且仅当浅井惠的行动序列的影响度大于变革者的行动序列的影响度。双方各选取一个行动序列，问有多少种选取方案使得浅井惠可以阻止变革。两种选取方案不同当且仅当存在至少一方在两个方案中选择了不同的行动序列。答案对$998244353$取模。
Input
第$1$行两个整数$n,m$，分别代表序列$a,b$的长度。
第$2$行$n$个用空格隔开的整数$a_i$。
第$3$行$m$个用空格隔开的整数$b_i$。
$1 \le n,m \le 5000$
$1 \le a_i,b_i \le 100$
第$2$行$n$个用空格隔开的整数$a_i$。
第$3$行$m$个用空格隔开的整数$b_i$。
$1 \le n,m \le 5000$
$1 \le a_i,b_i \le 100$
Output
一个整数代表。
Sample Input
3 5 2 1 2 1 2 2 1 2
Sample Output
22
Source
642ccpcQHD
Hint
浅井惠可以采取(1),(2),(1,2),(2,1),(2,2),(2,1,2)共6种行动序列。
变革者可以采取(1),(2),(1,1),(1,2),(2,1),(2,2),(1,1,2),(1,2,1),(1,2,2),(2,1,2),(2,2,2)共11种行动序列。
若双方各取一个行动序列，则共有22种方案使得浅井惠的行动序列的影响度更大。