CF217D Bitonix' Patrol

比特兰正试图向 Bit-X 行星发射一项太空任务。但他们的任务受到了麻烦，因为该行星的轨道上会定期被 Bit-X 太空部队的队长比托尼克斯（Bitonix）巡逻。 Bit-X 行星的周围有 $n$ 个空间站，按顺时针方向编号，从 1 到 $n$。这些空间站均匀分布在一个圆形轨道上，因此编号为 $i$ 和 $i+1$（$1 \leq i < n$）的空间站，以及编号为 1 和 $n$ 的空间站，是相邻的。每一对相邻空间站之间的距离都是 $m$ 光里。为了巡逻，比托尼克斯会从某个空间站起飞，并沿着圆形轨道飞行，所经过的距离至少为 1 光里，并最终停在某一个空间站（可能是他出发的那个）。 比托尼克斯的火箭通过燃烧燃料箱来移动。当他安装一个容量为 $x$ 升的燃料箱并选择方向（顺时针或逆时针）后，火箭会沿着圆形轨道朝所选方向恰好飞行 $x$ 光里。注意火箭没有刹车装置，只有等燃料箱耗尽才能停下。 举个例子，假如 $n=3$，$m=60$，而比托尼克斯拥有容量为 10、60、90 和 100 升的燃料箱。如果他从 1 号空间站出发，使用 100 升的燃料箱顺时针飞行，再用 90 升的燃料箱顺时针飞行，最后用 10 升的燃料箱逆时针飞行，他就会回到 1 号空间站。这构成一次有效的巡逻。注意比托尼克斯并不需要用完所有的燃料箱。在这个例子中，他也可以只用 60 升燃料箱，飞向 2 号或 3 号站，这也是一个有效的巡逻。 然而，如果 $n=3$，$m=60$，而比托尼克斯仅有一个 10 升和一个 100 升的燃料箱，那么他就无法完成任何有效巡逻（因为他不可能精确地停在某个空间站）。 比特兰太空局希望摧毁比托尼克斯的一些燃料箱，使他无法再完成任何有效巡逻。请你计算有多少种不同的燃料箱子集（即摧毁方案），可以让比托尼克斯无法再完成巡逻，并输出方案数模 $1000000007$（$10^9+7$）。

第一行输入三个整数 $n$（$2 \leq n \leq 1000$）——空间站数量，$m$（$1 \leq m \leq 120$）——相邻空间站间距离，以及 $t$（$1 \leq t \leq 10000$）——比托尼克斯拥有的燃料箱数量。 第二行输入 $t$ 个用空格分隔的整数，表示每个燃料箱的容量（介于 $1$ 和 $10^9$ 之间），每个燃料箱彼此不同（即使容量相同也视为不同的箱子）。

输出一个整数，表示可以摧毁的不同燃料箱集合的数量，从而使比托尼克斯无法完成巡逻。结果对 $10^9+7$ 取模。

所有燃料箱都是互不相同的，即使它们容量相同也当做不同物品处理。 由 ChatGPT 5 翻译