Thue-Morse-Radecki-Mateusz 序列(简称 Thorse-Radewoosh 序列)是由长度为 $$$d$$$ 的有限序列 $$$\mathrm{gen}$$$ 和整数 $$$m$$$ 构造的无限序列,通过以下步骤序列获得:
- 一开始,我们定义单元素序列 $$$M_0=(0)$$$。
- 在第 $$$k$$$ 步骤 $$$k \geq 1$$$ 中,我们将序列 $$$M_k$$$ 定义为 $$$M_{k-1}$$$ 的 $$$d$$$ 副本的串联。然而,它们中的每一个都略有改变 - 在它们的第 $$$i$$$ 中 ($$$1 \leq i \leq d$$$),每个元素 $$$x$$$ 更改为 $$$(x+\mathrm{gen}_i) \pmod{m}$$$。
例如,如果我们选择 $$$\mathrm{gen} = (0, \color{blue}{1}, \color{green}{2})$$$ 和 $$$m = 4$$$:
- $$$M_0 = (0)$$$,
- $$$M_1 = (0, \color{蓝色}{1}, \color{绿色}{2})$$$,
- $$$M_2 = (0, 1, 2, \color{蓝色}{1, 2, 3}, \color{绿色}{2, 3, 0})$$$,
- $$$M_3 = (0, 1, 2, 1, 2, 3, 2, 3, 0, \color{蓝色}{1, 2, 3, 2, 3, 0, 3, 0, 1}, \color{绿色}{2, 3, 0, 3, 0, 1, 0, 1, 2})$$$,等等上。
可以看到,只要$$$\mathrm{gen}$$$的第一个元素是$$$0$$$,连续的每一步都会产生一个序列,其前缀就是上一步生成的序列。因此,我们可以将无限Thorse-Radewoosh序列$$$M_\infty$$$定义为无限应用上述步骤得到的序列。对于上面的参数,$$$M_\infty = (0, 1, 2, 1, 2, 3, 2, 3, 0, 1, 2, 3, 2, 3, 0, 3, 0, 1, \dots)$$$。
Mateusz 选择了一个序列 $$$\mathrm{gen}$$$ 和一个整数 $$$m$$$,并使用它们获得了 Thorse-Radewoosh 序列 $$$M_\infty$$$。然后,他选择了两个整数 $$$l$$$、$$$r$$$,并写下了该序列 $$$A := ((M_\infty)_l, (M_\infty)_{l+1}, \dots, (M_\infty)_r)$$$ 的子序列。
请注意,我们对 $$$M_\infty$$$ 和 $$$A$$$ 使用基于 $$$1$$$ 的索引。
Mateusz 有他最喜欢的序列 $$$B$$$,长度为 $$$n$$$,并且想看看它与 $$$A$$$ 相比有多大。假设 $$$B$$$ 优先考虑长度为 $$$n$$$ 的序列 $$$X$$$(我们将其表示为 $$$B \geq X$$$)当且仅当对于所有 $$$i \in \{1, 2, \dots, n\}$$$,我们有 $$$B_i \geq X_i$$$。
他现在问自己 $$$x$$$ 范围内有多少个整数 $$$[1, |A| - n + 1]$$$ 存在 $$$B \geq (A_x, A_{x+1}, A_{x+2}, \dots, A_{x+n-1})$$$。由于两个序列都很大,仅用笔和纸回答问题太耗时了。你能帮助他自动化他的研究吗?
输入
第一行包含两个整数 $$$d$$$ 和 $$$m$$$ ($$$2 \leq d \leq 20$$$, $$$2 \leq m \leq 60$$$) — 序列 $$$\mathrm{gen}$$$ 的长度和用于执行模运算的整数。第二行包含 $$$d$$$ 整数 $$$\mathrm{gen}_i$$$ ($$$0 \leq \mathrm{gen}_i < m$$$)。保证序列 $$$\mathrm{gen}$$$ 的第一个元素等于 0。
第三行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 30000$$$) — 序列 $$$B$$$ 的长度。第四行包含 $$$n$$$ 整数 $$$B_i$$$ ($$$0 \leq B_i < m$$$)。第五行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l \leq r \leq 10^{18}$$$, $$$r-l+1 \geq n$$$)。
输出
打印一个整数——问题的答案。
示例
输入 #1
2 2 0 1 4 0 1 1 0 2 21
输出 #1
6
输入 #2
3 4 0 1 2 2 0 2 6 11
输出 #2
1
注意
第一个示例中的Thorse-Radewoosh序列是标准Thue-Morse序列,因此序列$$$A$$$如下:$$$11010011001011010010$$$。以下是序列 $$$B$$$ 优先于 $$$A$$$ 的地方: