[ZSHOI-R1] 有效打击

打腻了原版的 Boss，FyFive 决定做一个 Hollow Knight Mod Boss，名字叫“成功冠军”。

和原本的失败冠军类似，成功冠军也有一个不能回魂的大盔甲。但是成功冠军更难的地方在于：它的盔甲需要以特定的打击方式才能造成伤害，可以造成伤害的打击序列被称作“有效打击”。 作为 Mod Boss 的设计者，FyFive 设置了一个可以造成有效打击的“标准序列”。为了降低操作难度，当打击顺序与标准序列“相似”时，即可造成有效打击。在这里“相似”的定义是，对于一个打击序列，将所有相同打击的连续段的长度同时进行放缩，可以得到另一个序列，则称这两个序列是“相似”的。 例如： - ``112244`` 和 ``111222444`` 是相似的， - ``111333`` 和 ``13`` 也是相似的， - ``226`` 和 ``226`` 也是相似的， - ``33889`` 和 ``33388899`` 则不是相似的。 由于 Boss 还处在调整标准序列的阶段，所以 FyFive 将 Boss 的血量调到了无穷大，但这样他就没办法通过比较初始血量和最终血量来计算他的打击序列在当前标准序列下能造成多少次有效打击，所以请万能的你来帮帮 FyFive 吧！ **注意**：对于可能出现的同时造成多次有效打击的情况，会造成多次有效打击，比如当打击序列为 ``11`` 时，若标准序列为 ``1``，则这个打击序列会造成 $3$ 次有效打击，因为第一个 ``1`` 和第二个 ``1`` 均与标准序列相似，同时 ``11`` 也与标准序列相似。若标准序列为 ``11``则也有 $3$ 次有效打击。若标准序列为 ``12``，则不会造成有效打击。同理，当打击序列为 ``6666``，标准序列为 ``66`` 时，则一共会造成 $10$ 次有效打击。 #### 形式化的， >定义：若序列 $\Alpha$ 为 > $$\underbrace{AA...A}_{a_1个}\underbrace{BB...B}_{a_2个}\underbrace{CC...C}_{a_3个}...$$ > 序列 $\Beta$ 为 > $$\underbrace{AA...A}_{b_1个}\underbrace{BB...B}_{b_2个}\underbrace{CC...C}_{b_3个}...$$ > 其中 $A,B,C,a_1,a_2,a_3,...,b_1,b_2,b_3,...\in N_+$。 > > 若有 $\frac{a_1}{b_1}=\frac{a_2}{b_2}=\frac{a_3}{b_3}=...=k\ , k>0$，则称 $\Alpha$ 与 $\Beta$ 互为相似序列。 > > 特别的，长度为 $0$ 的序列不与任何序列成相似序列。 > > 不难证明此定义下序列间的相似具有传递性。 求给定的序列 $A$ 中有多少个子串与给定序列 $B$ 互为相似序列。

第一行两个整数 $n,m$。 第二行 $n$ 个整数，表示打击序列 $A$，数之间用空格隔开。 第三行 $m$ 个整数，表示标准序列 $B$，数之间用空格隔开。

一行一个正整数，表示造成的有效打击总数。

7 3
6 7 6 6 6 5 4
6 6 6

7

8 6
4 4 2 2 4 4 2 2
4 4 4 4 2 2

2

8 7
3 3 3 2 2 2 1 1
3 3 3 2 2 2 1

1

数据范围： | 数据点 | n | m | 特殊性质 | | :----------: | :----------: | :----------: | :----------: | | 1~2 | $\leq 20000$ | $\leq 20000$ | 无 | | 3~4 | $\leq 5 \times 10^6$ | $\leq 5 \times 10^6$ | A | | 5~6 | $\leq 5 \times 10^6$ | $\leq 5 \times 10^6$ | B | | 7~10 | $\leq 5 \times 10^6$ | $\leq 5 \times 10^6$ | C | 对于 $100\%$ 的数据，保证有 $\forall\ i\in[1,n]$，$1\leq A_i \leq 7$；$\forall\ i\in[1,m]$，$1\leq B_i\leq 7$。 对于 $100\%$ 的数据，保证 $1\leq n,m\leq 5 \times 10^6$。 特殊性质 A：保证 $\forall\ i,j\in [1,m]，B_i=B_j$。 特殊性质 B：保证有且仅有一个 $k\in[1,m-1]$，使得 $\forall \ i,j\in[1,k]$，$B_i=B_j$；$\forall \ i,j\in[k+1,m]$，$B_i=B_j$。 特殊性质 C：保证第 $10$ 个点中 $n,m \leq 5\times 10^5$，且其他点中连续段仅有不超过 $100$ 种不同的长度。