F. Пловцы в бассейне
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В бассейне длины $$$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
Примечание

В первом примере три момента встречи:

  • момент $$$6$$$, в который оба пловца в точке $$$6$$$;
  • момент $$$12$$$, в который оба пловца в точке $$$6$$$;
  • и момент $$$18$$$, в который оба пловца в точке $$$0$$$.