Tại một ngôi làng nhỏ ở Lộc Hà, có \(N\) ngôi nhà xếp thành một hàng. Ngôi nhà thứ \(i\) có \(a_i\) thành viên trong gia đình. Để tăng thu nhập cho làng, trưởng làng tổ chức một chương trình. Mỗi ngày, ông sẽ chọn đúng \(K\) nhóm nhà sao cho:

• Mỗi nhóm gồm ít nhất một ngôi nhà.

• Mỗi ngôi nhà chỉ thuộc về một nhóm duy nhất.

• Các ngôi nhà trong cùng một nhóm phải nằm liền kề nhau.

Sau đó, mỗi nhóm sẽ quyên góp một số tiền bằng với Ước chung lớn nhất (GCD) của số thành viên trong tất cả các ngôi nhà trong nhóm đó. Trưởng làng sẽ luôn chọn cách phân nhóm khác nhau mỗi ngày. Lễ hội kết thúc khi tất cả các cách phân nhóm K nhóm khác nhau đã được thực hiện.

Yêu cầu: Tính tổng số tiền quyên góp được sau lễ hội là bao nhiêu. Do kết quả có thể rất lớn, hãy trả lời phần dư của kết quả chia cho 10^9+7.

Input

• Dòng đầu tiên chứa hai số nguyên \(N,K(1≤N≤5×10^4;1≤K≤min⁡(N,20) ).\)

• Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,…,a_(N ) (1≤a_i≤10^5).\)

Output

• Một dòng duy nhất in tổng thu nhập thu được sau toàn bộ lễ hội, chia dư cho \(10^9+7\).

Ràng buộc

• Subtask 1: 10% điểm: \(N≤10\).

• Subtask 2: 10% điểm: \(N≤500,K=1.\)

• Subtask 3: 10% điểm: \(N≤500,K≤2. \)

• Subtask 4: 20% điểm: \(K=1.\)

• Subtask 4: 20% điểm: \(a_1=a_2=⋯=a_N.\)

• Subtask 6: 30% điểm: Không có ràng buộc gì thêm.

Sample Input

3 2
6 4 5

Sample Output

44

Giải thích:

Các cách chia nhóm và thu nhập tương ứng:

• [6] [4] 5 → 6 + 4 = 10

• [6] 4 [5] → 6 + 5 = 11

• [6] [4 5] → 6 + 1 = 7

• [6 4] [5] → 2 + 5 = 7

• 6 [4] [5] → 4 + 5 = 9

Tổng cộng: 10 + 11 + 7 + 7 + 9 = 44