Cho đoạn ~[L, R]~ và ~k~ số nguyên dương ~a_1, a_2, \dots, a_k~. Hãy tính tổng tất cả các số nguyên trong đoạn ~[L, R]~ chia hết cho ít nhất một trong ~k~ số đã cho.

Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho ~10^9 + 7~.

Input:

• Dòng thứ nhất chứa ba số nguyên ~L~, ~R~ và ~k~.
• Dòng thứ hai chứa ~k~ số nguyên ~a_1, a_2, \dots, a_k~.

Output:

Một số nguyên duy nhất là tổng cần tìm sau khi lấy phần dư cho ~10^9 + 7~.

Ràng buộc:

~1 \le L \le R \le 10^{18}~, ~1 \le k \le 15~, ~1 \le a_i \le 10^{18}~.

• Subtask 1 (20% số điểm): ~k = 1~.
• Subtask 2 (30% số điểm): ~R \le 10^6~ và ~k \le 10~.
• Subtask 3 (50% số điểm): không có ràng buộc bổ sung.

Ví dụ:

Input

1 10 2
3 5

Output

33

Input

1 20 3
2 3 5

Output

142

Giải thích ví dụ 1: các số chia hết cho ~3~ hoặc ~5~ trong ~[1, 10]~ là ~3, 5, 6, 9, 10~, tổng bằng ~33~.