Trọng đang làm phụ bếp tại tiệm bánh Bedao. Để làm được một chiếc bánh, Trọng phải sử dụng một số bột ~N~ để làm thành một chiếc bánh có nhiều tầng sao cho tổng số bột của các tầng bằng ~N~.

Bếp trưởng cho biết chiếc bánh sẽ có một giá trị hạnh phúc ~G(A)~ được tính bằng tích số bột của các tầng. Tức là nếu Trọng chia ~N~ bột bánh thành ~n~ tầng có giá trị số bột là một dãy ~A~, giá trị hạnh phúc sẽ là hàm tích ~\displaystyle G(A) = \prod_{i=1}^{n} A_i~ với điều kiện tổng số bột bánh ~\displaystyle F(A) = \sum_{i=1}^{n} A_i~ là ~N~.

Ở sự kiện Bedao OI lần này, Trọng được giao trách nhiệm phải làm ra các loại bánh có tổng bột nằm trong vùng kiểm định cho phép ~N \in [L, R]~.

Do muốn gây ấn tượng với bếp trưởng, Trọng quyết định sẽ làm ra tất cả các loại bánh có thể sao cho mỗi chiếc bánh sử dụng đúng theo yêu cầu kiểm định, sao cho không có bánh nào giống nhau. Ngoài ra Trọng còn đề ra tiêu chí thẩm mỹ của bánh, sao cho số bột của mỗi tầng trong bánh phải chia hết cho ít nhất một phần tử trong tập hợp ~K~.

Ví dụ: Với ~L = 7, R = 9, K = \{2,3\}~, Trọng có thể xây thành các loại bánh như ~(2,2,3)~ hay ~(6,3)~ với giá trị hạnh phúc lần lượt là ~2 \times 2 \times 3 = 12~ và ~6 \times 3 = 18~.

Trọng muốn biết là tổng giá trị hạnh phúc của tất cả các loại bánh có thể làm được. Bạn hãy giúp Trọng nhé!

Do giá trị có thể rất lớn nên đáp án trả về dưới dạng chia lấy phần dư cho ~10^9 + 7~. Hai cách xây bánh ~A^{\prime}~ và ~A^{\prime\prime}~ được coi là riêng biệt nếu như ~|A^{\prime}| \neq |A^{\prime\prime}|~ hoặc tồn tại một vị trí ~i~ sao cho ~A^{\prime}_i \neq A^{\prime\prime}_i~.

Ví dụ: ~(1, 2, 3)~ khác với ~(2, 3, 4)~, và ~(1, 1, 2)~ khác với ~(1, 2, 1)~.

Input

Dữ liệu vào từ file văn bản a.inp:

• Dòng đầu tiên chứa hai số nguyên dương ~L~ và ~R~ ~(1 \leq L \leq R \leq 10^{18})~.

• Dòng thứ hai chứa số nguyên dương ~m~ thể hiện số lượng phần tử trong tập hợp ~K~.

• Dòng thứ ba chứa ~m~ số nguyên dương phân biệt ~K_i~ ~(LCM(K_1, \ldots ,K_m) \leq 80)~.

Output

In ra file văn bản a.out một số nguyên duy nhất là tổng giá trị hạnh phúc của tất cả loại bánh có thể làm được chia lấy phần từ cho ~10^9 + 7~.

Scoring

Sample Input 1

3 4
2
2 3

Sample Output 1

11

Sample Input 2

2 3
1
1

Sample Output 2

11

Notes

Ở ví dụ ~1~, ta có những dãy thoả mãn là ~(2,2),~ ~(3)~ và ~(4)~, tổng giá trị hạnh phúc là ~2\times 2 + 3 + 4 = 11~.

Ở ví dụ ~2~, ta có những dãy thoả mãn là ~(1,1),~ ~(1,1,1),~ ~(1,2),~ ~(2),~ ~(2,1),~ và ~(3)~, tổng giá trị hạnh phúc là ~1 + 1\times 1 + 1\times 2 + 2\times 1 + 2 + 3 =11~.