В бассейне длины $$$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$$$.
9 18 2 1 2
3
12 13 3 4 2 6
10
1 1000000000 3 100000 150000 200000
997200007
В первом примере три момента встречи:
Название |
---|