Trong hành trình khai phá sao Hỏa năm 3000, người ta phát hiện rằng đã bắt đầu có dấu hiệu rõ ràng của sự sống trên hành tinh này. Sau khi tiến hành một cuộc rà soát diện rộng, người ta tìm được \(n\) sinh vật trên hành tinh này, các sinh vật được đánh số từ \(1\) đến \(n\), sinh vật thứ \(i\) \((1 \leq i \leq n)\) được gán cho một nhãn \(a_i\) dựa vào các đặc tính của nó.

Khi mẫu vật của \(n\) sinh vật được đưa về Trái Đất, các nhà khoa học tiến hành nghiên cứu các sinh vật này. Một trong những vấn đề được quan tâm hàng đầu là dựa vào các đặc tính đã biết của các sinh vật để nghiên cứu sự tương tác giữa các sinh vật trên với nhau, từ đó có thể phát hiện ra được nhiều đặc tính hơn nữa.

Mỗi lần lấy mẫu, người ta có thể chọn ra một số các sinh vật có chỉ số \(i_1, i_2, \ldots, i_k\) \((0 < k \leq n, 1 \leq i_1 < i_2 < \ldots < i_k \leq n)\). Người ta gọi mức hòa hợp của các sinh vật được chọn là \(\gcd(a_{i_1}, a_{i_2}, \ldots, a_{i_k}) \times \min(a_{i_1}, a_{i_1 + 1}, a_{i_1+2}, \ldots, a_{i_k})\).

Rõ ràng có \(2^n - 1\) cách chọn ra một số các sinh vật. Hai cách chọn được coi là khác nhau nếu tồn tại một sinh vật mà được chọn trong cách này nhưng không được chọn trong cách kia.

Yêu cầu: Hãy tính tổng mức hòa hợp của \(2^n - 1\) cách chọn ra các sinh vật như trên.

Input

• Dòng đầu tiên gồm một số nguyên dương \(n\) \((1 \leq n \leq {10}^5)\).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq {10}^5)\).

Output

• Gồm duy nhất một số nguyên dương là tổng mức hòa hợp của tất cả \(2^n - 1\) cách chọn ra một số các sinh vật khác nhau, vì kết quả có thể rất lớn nên chỉ cần đưa ra số dư của tổng mức hòa hợp khi chia cho \(({10}^9 + 7)\).

Scoring

• Subtask 1 (\(11\%\) số điểm): \(n \leq 100, a_i \leq 100\).
• Subtask 2 (\(13\%\) số điểm): \(n \leq 2000\).
• Subtask 3 (\(15\%\) số điểm): \(\gcd(a_i, a_j) = 1\), \(\forall 1 \leq i, j \leq n\) và \(i \neq j\).
• Subtask 4 (\(17\%\) số điểm): \(a_i = i\), \(\forall 1 \leq i \leq n\).
• Subtask 5 (\(21\%\) số điểm): \(a_i = 2^k\) \((0 \leq k < 17)\), \(\forall 1 \leq i \leq n\).
• Subtask 6 (\(23\%\) số điểm): Không có ràng buộc gì thêm.

Example

1
10

100

3
1 2 3

19

2
2 4

24