背景

题目来源：【HT-122-Div.3】核桃 CSP-J 组模拟赛

题目描述

Red Face 有一个长度为 $n$ 的数组 $a$。

现在，Red Face 需要选择一个同样长度为 $n$ 数组 $b$。对于数组 $b$ 中的每一个元素 $b_i$，都必须满足：

也就是说，$b_i$ 可以选择为 $-k$ 到 $k$ 之间的任意一个整数，包括 $-k$ 和 $k$。

在确定数组 $b$ 后，Red Face 会根据数组 $a$ 和数组 $b$ 构造出一个新的长度为 $n$ 的整数数组 $c$。对于每一个位置 $i$，数组 $c$ 的元素满足：

你需要计算，一共有多少种不同的数组 $b$，能够使构造出的数组 $c$ 全部相等。也就是说，需要满足：

请输出满足上述条件的方案数。

输入格式

第一行输入一个正整数 $n,k$ 表示数组长度，和可选数字范围。

第二行输入 $n$ 个正整数 $a_i$。

输出格式

输入一行一个整数，表示答案。

5 2
2 3 4 2 3

3

提示

样例解释

对于样例 $1$：

所有 $c_i$ 可以同时取 $2,3,4$，因此共有 $3$ 种方案。

对应的数组 $b$ 分别为：

• 当所有 $c_i=2$ 时，$b=\{0,-1,-2,0,-1\}$；
• 当所有 $c_i=3$ 时，$b=\{1,0,-1,1,0\}$；
• 当所有 $c_i=4$ 时，$b=\{2,1,0,2,1\}$。

以上数组中的每个 $b_i$ 均满足 $b_i \in [-2,2]$。

数据规模与约定

::cute-table{tuack} | 测试点编号 | $n \le$ | | :----------: | :-------------: | | $1 \sim 4$ | $10$ | | $5 \sim 8$ | $500$ | | $9 \sim 12$ | $2000$ | | $13 \sim 16$ | $2 \times 10^5$ | | $17 \sim 20$ | $10^6$ |

对于 $100\%$ 的测试点，保证：

• $1 \le n \le 10^6$
• $1 \le a_i,k \le 10^9$