Tại UMT, một nhóm bạn đang chuẩn bị cho một buổi tiệc và muốn chia thành các nhóm con để thảo luận về sở thích chung. Mỗi người bạn có một số nguyên dương đại diện cho sở thích của họ. Họ muốn tìm ra số lượng cặp nhóm con không rỗng (A, B) thỏa mãn các điều kiện sau:

• A và B là các dãy con (không nhất thiết liên tiếp) của danh sách ban đầu.

• A và B không có phần tử chung.

• Ước chung lớn nhất (GCD) của các phần tử trong A bằng GCD của các phần tử trong B.

Nhiệm vụ của bạn là tính số lượng cặp nhóm con như vậy. Do kết quả có thể rất lớn, hãy trả về kết quả MOD ~10^9 + 7~.

Input

Dòng đầu tiên chứa một số nguyên ~n~ ~(1 ≤ n ≤ 500)~ — số lượng người bạn.

Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, . . . , a_n (1 ≤ a_i ≤ 500)~ — đại diện cho sở thích của từng người bạn.

Output

In ra một số nguyên duy nhất — số lượng cặp nhóm con thỏa mãn điều kiện, MOD ~10^9 + 7~.

Sample Input 1

3
2 1 3

Sample Ouput 1

2

Sample Input 2

4
1 1 1 1

Sample Ouput 2

50

Giải thích

Trong test đầu, A = {2, 3}, B = {1} và A = {1}, B = {2, 3}. Trong test hai, Do các phần tử đều giống nhau nên đáp án là [ \sum_{i=1}^{3} \binom{4}{i} \cdot \left(2^{4 - i} - 1\right) ]

Subtask:

• Subtask 1 (5% số điểm): ~a_i = 1~.

• Subtask 2 (20% số điểm): ~n ≤ 20~.

• Subtask 3 (75% số điểm): Không giới hạn gì thêm.