← 返回题目列表

Codeforces · 1845/F

F. 泳池里的游泳者

中文机器翻译题面 查看原题

有一个长度为 $$$l$$$ 的泳池,$$$n$$$ 游泳者计划在那里游泳。人们同时开始游泳(在$$$0$$$时刻),但你可以假设他们走不同的泳道,这样他们就不会互相干扰。

每个人沿着以下路线游泳:他们从点$$$0$$$开始,以恒定速度游到点$$$l$$$(对于第$$$i$$$个游泳者来说,等于每秒$$$v_i$$$个单位)。到达$$$l$$$点后,游泳者立即(在可忽略的时间内)返回并以相同的恒定速度开始游向$$$0$$$点。返回到点$$$0$$$后,游泳者开始游向点$$$l$$$,依此类推。

假设某个真实的时刻是相遇时刻,如果在该时刻至少有两个游泳者位于泳池的同一点(该点可以是 $$$0$$$ 或 $$$l$$$ 以及泳池内的任何其他真实点)。

矿池将开放 $$$t$$$ 秒。您必须计算泳池开放时的会议时刻数。由于答案可能非常大,因此打印它对 $$$10^9 + 7$$$ 取模。

输入

第一行包含两个整数 $$$l$$$ 和 $$$t$$$ ($$$1 \le l, t \le 10^9$$$) - 池的长度和过程的持续时间(以秒为单位)。

第二行包含单个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 游泳者的数量。

第三行包含 $$$n$$$ 整数 $$$v_1, v_2, \dots, v_n$$$ ($$$1 \le v_i \le 2 \cdot 10^5$$$),其中 $$$v_i$$$ 是第 $$$i$$$ 位游泳者的速度。所有 $$$v_i$$$ 都是成对不同的。

输出

打印一个整数 - 会议时刻的数量(如果需要,包括时刻 $$$t$$$,不包括时刻 $$$0$$$),以 $$$10^9 + 7$$$ 为模。

示例

输入 #1

9 18
2
1 2

输出 #1

3

输入 #2

12 13
3
4 2 6

输出 #2

10

输入 #3

1 1000000000
3
100000 150000 200000

输出 #3

997200007

注意

在第一个示例中,存在三个会议时刻:

- 时刻$$$6$$$,在此期间两名游泳者都处于$$$6$$$点;
- 时刻$$$12$$$,在此期间两名游泳者都处于点$$$6$$$;
- 以及 $$$18$$$ 时刻,在此期间,两名游泳者都处于 $$$0$$$ 点。