CF1845F.Swimmers in the Pool

There is a pool of length $l$ where $n$ swimmers plan to swim. People start swimming at the same time (at the time moment $0$ ), but you can assume that they take different lanes, so they don't interfere with each other.

Each person swims along the following route: they start at point $0$ and swim to point $l$ with constant speed (which is equal to $v_i$ units per second for the $i$ -th swimmer). After reaching the point $l$ , the swimmer instantly (in negligible time) turns back and starts swimming to the point $0$ with the same constant speed. After returning to the point $0$ , the swimmer starts swimming to the point $l$ , and so on.

Let's say that some real moment of time is a meeting moment if there are at least two swimmers that are in the same point of the pool at that moment of time (that point may be $0$ or $l$ as well as any other real point inside the pool).

The pool will be open for $t$ seconds. You have to calculate the number of meeting moments while the pool is open. Since the answer may be very large, print it modulo $10^9 + 7$ .

The first line contains two integers $l$ and $t$ ( $1 \le l, t \le 10^9$ ) — the length of the pool and the duration of the process (in seconds).

The second line contains the single integer $n$ ( $2 \le n \le 2 \cdot 10^5$ ) — the number of swimmers.

The third line contains $n$ integers $v_1, v_2, \dots, v_n$ ( $1 \le v_i \le 2 \cdot 10^5$ ), where $v_i$ is the speed of the $i$ -th swimmer. All $v_i$ are pairwise distinct.

Print one integer — the number of meeting moments (including moment $t$ if needed and excluding moment $0$ ), taken modulo $10^9 + 7$ .

In the first example, there are three meeting moments:

• moment $6$ , during which both swimmers are in the point $6$ ;
• moment $12$ , during which both swimmers are in the point $6$ ;
• and moment $18$ , during which both swimmers are in the point $0$ .