有一个长度为 $$$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$$$ 点。