时空限制

1S/512M

题目描述

给定两个整数数组 $A$ 和 $B$，长度分别为 $n$ 和 $m$。以及一个整数 $K$。

你需要从数组 $A$ 中选出一个子序列，使得这个子序列恰好等于序列 $B$。 但是在选取时，有一个额外的限制：相邻两个被选中元素的原始下标之差必须至少为 $K$。

请计算有多少种满足条件的选取方案。由于答案可能很大，请输出答案对 $998244353$ 取模的结果。

格式

输入格式

第一行包含三个正整数 $n, m, K$，分别表示数组 $A$ 的长度，数组 $B$ 的长度以及间隔限制。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示数组 $A$。

第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$，表示数组 $B$。

输出格式

输出一行一个整数，表示满足条件的方案数模 $998244353$ 的结果。

样例

样例输入 #1

5 2 2
1 3 3 2 2
1 2

样例输出 #1

2

样例解释 #1

满足条件的方案的下标是 $[1,4]$，$[1,5]$。

故总共有 $2$ 种方案。

样例输入 #2

6 3 2
1 10 2 10 3 10
1 2 3

样例输出 #2

1

数据规模

对于 $40\%$ 的数据，$1 \le n \le 200$。

对于 $100\%$ 的数据，$1 \le n \le 5000$， $1 \le m \le n$， $1 \le K \le n$。 $1 \le A_i, B_i \le n$。