406321: GYM102361 C Sakurada Reset

A huge revolution is coming up in Sakurada. In order to avoid the revolution, Asai Kei is going to take some actions. The director of the revolution will also take some actions to defend Asai Kei. In this problem, each action can be described as a positive integer.

Specifically, Asai Kei will choose a non-empty subsequence as the actual actions to take from a given sequence $$$a$$$. Meanwhile, the director will similarly choose a non-empty subsequence as the defending actions from a given sequence $$$b$$$. And the influence value of a sequence of actions $$$p_1, p_2, \cdots, p_k$$$ of length $$$k$$$ is defined as follows: $$$$$$\sum_{i=1}^{k} p_i \times 1000^{k-i}$$$$$$

Now given action sequences $$$a$$$ and $$$b$$$, Asai Kei will choose a non-empty subsequence $$$A$$$ from $$$a$$$ and the director will choose a non-empty subsequence $$$B$$$ from $$$b$$$. Asai Kei can beat the director if and only if the influence value of $$$A$$$ is strictly greater than $$$B$$$.

You want to know the number of different schemes for them to choose subsequences $$$A$$$ and $$$B$$$ so that Asai Kei can beat the director. Two schemes $$$(A_1, B_1), (A_2, B_2)$$$ are considered to be different if $$$A_1 \neq A_2$$$ or $$$B_1 \neq B_2$$$, and two sequences $$$p, q$$$ are considered to be different if their influence values are different. Print the answer modulo 998244353 in a single line.

The first line contains two positive integers $$$n,m~(1\le n,m \le 5\,000)$$$, denoting the length of $$$a$$$ and the length of $$$b$$$.

The next line contains $$$n$$$ positive integers $$$a_i~(1\le a_i \le 100)$$$, denoting the sequence $$$a$$$.

The next line contains $$$m$$$ positive integers $$$b_i~(1\le b_i \le 100)$$$, denoting the sequence $$$b$$$.

Output a single line containing a non-negative integer, denoting the answer modulo 998244353.

3 5
2 1 2
1 2 2 1 2

22

Asai Kei can choose 6 subsequences: (1), (2), (1,2), (2,1), (2,2), (2,1,2), and their influence values are 1, 2, 1002, 2001, 2002, 2001002 respectively. The director can choose 11 subsequences: (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), and their influence values are 1, 2, 1001, 1002, 2001, 2002, 1001002, 1002001, 1002002, 2001002, 2002002 respectively.

There are $$$0+1+3+4+5+9=22$$$ schemes in total that Asai Kei can beat the director.