1.# 子序列
## 题目描述
给定两个整数序列，第一个序列长度为 n*n*，第二个序列长度为 m*m*。请问，这两个序列有多少种公共的子序列？输出数量模 998244353998244353 的余数。
所谓子序列，是指从原序列中选择部分或全部元素组成新序列，这些元素在原序列中不必连续，但要保持在原序列中的顺序。只要下标不同，哪怕数字相同，也要算成不同的子序列。
## 输入格式
· 第一行：两个整数表示 n*n* 与 m*m*；
· 第二行： n*n* 个数字 a1,a2,⋯ ,an*a*1,*a*2,⋯,*an*；
· 第三行：m*m* 个数字 b1,b2,⋯ ,bm*b*1,*b*2,⋯,*bm*；
## 输出格式
单个整数表示答案。
## 输入样例
4 3
3 4 6 2
3 3 2
## 输出样例
6
## 说明提示
· 1≤n,m≤20001≤*n*,*m*≤2000
· 1≤ai,bj≤100,0001≤*ai*,*bj*≤100,000
## 限制
时间限制：1000ms
内存限制：512MiB

这道题目可以使用动态规划来解决。我们可以定义一个二维数组dp，其中dp[i][j]表示第一个序列的前i个元素和第二个序列的前j个元素之间的公共子序列的数量。初始化dp[0][j]和dp[i][0]为0，表示空序列的公共子序列数量为0。然后我们可以使用动态规划的方式计算dp数组的值。对于每个元素ai和bj，我们可以选择将其包含在当前的子序列中，或者不包含在当前的子序列中。如果选择将其包含在当前的子序列中，那么我们就需要考虑前一个元素的状态。如果选择不包含在当前的子序列中，那么当前子序列的数量就与不包含前一个元素时的子序列数量相同。因此，我们可以得到状态转移方程：dp[i][j] = dp[i-1][j-1] + dp[i-1][j]（如果ai等于bj）或dp[i][j] = dp[i-1][j]（如果ai不等于bj）。最后，我们只需要输出dp[n][m]即可得到答案。为了优化空间复杂度，我们可以使用状态压缩的方式存储dp数组。由于题目要求输出数量模998244353的余数，我们可以在计算过程中一直对结果取模，避免结果溢出。