试题编号： 202104-4 试题名称： 校门外的树 时间限制： 1.0s 内存限制： 512.0MB 问题描述： 问题描述 X 校最近打算美化一下校园环境。前段时间因为修地铁，X 校大门外种的行道树全部都被移走了。现在 X 校打算重新再种一些树，为校园增添一抹绿意。

X 校大门外的道路是东西走向的，我们可以将其看成一条数轴。在这条数轴上有 个障碍物，例如电线杆之类的。虽然障碍物会影响树的生长，但是障碍物不一定能被随便移走，所以 X 校规定在障碍物的位置上不能种树。 个障碍物的坐标都是整数；如果规定向东为正方向，则 个障碍物的坐标按照从西到东的顺序分别为 。X 校打算在 之间种一些树，使得这些树看起来比较美观。

X 校希望，在一定范围内，树应该是等间隔的。更具体地说，如果把 划分成一些区间 （），那么每个区间 内需要至少种一棵树，且该区间内种的树的坐标连同区间端点 应该构成一个等差数列。不同区间的公差，也就是树的间隔可以不相同。

例如，如果障碍物位于 这三处，那么我们可以选择在 和 分别种树，也可以选择在 等间隔种树。如果是分别在 和 种树，由于每个区间内至少要种一棵树，坐标 上必须种树；而 上的树可以按照 的间隔种下，也可以按照 的间隔种下。下图表示了这两种美观的种树方案，其中橙色的圆表示障碍物，绿色的圆表示需要在这个位置种树，箭头上的数字表示种下这棵树时对应的间隔为多少。

sample1_h.png 对区间 和 分别以 和 的间隔种树是美观的

sample2_h.png 对区间 和 分别以 的间隔种树也是美观的

而如果选择在 区间等间隔种树，我们只能以 的间隔种树，因为无论是选择间隔 或者间隔 ，都需要在坐标 上种树，而这个位置已经有障碍物了。下图分别表示了间隔为 时的种树情况，红色箭头表示不能在这里种树。

sample3_h.png 对区间 以 的间隔种树是美观的

sample4_h.png 对区间 以 的间隔种树是不美观的

sample5_h.png 对区间 以 的间隔种树也是不美观的

一般地，给定一个区间 ，对于树的坐标的集合 （），归纳定义 在 上是美观的：

如果 ，，并且存在一个公差 ，使得 中的元素按照从小到大的顺序排序后，可以构成一个公差为 的等差数列（显然，这个等差数列的首项为 ，末项为 ），则 在 上是美观的； 如果 ，并且存在一个下标 （），使得 在 上是美观的，且 在 上是美观的，则 在 上是美观的。 根据这一定义，空集在任意区间上都不是美观的；另外，如果存在下标 使得 ，那么 一定不是美观的。

我们称两种种树的方案是本质不同的，当且仅当两种方案中，种树的坐标集合不同。请帮助 X 校对 求出所有本质不同的美观的种树方案。当然，由于方案可能很多，你只需要输出总方案数对 取模的结果。

输入格式 输入的第一行包含一个正整数 ，表示障碍物的数量。

输入的第二行包括 个非负整数 ，表示每个障碍物的坐标。

保证对 ，。

输出格式 输出一个非负整数，表示本质不同的美观的种树方案的数量对 取模的结果。

样例输入 3 0 2 6 Data 样例输出 3 Data 样例说明 这组样例即为题面描述中提到的那组。

样例输入 11 0 10 20 30 40 50 60 70 80 90 100 Data 样例输出 256507