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. Trưởng làng muốn biết 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\)

Dữ liệu vào:

- Dòng đầu tiên: \(n\) và \(k\)

- Dòng thứ hai: \(a_{1},a_{2},\ldots,a_{n}\)

Kết quả:

- 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\).

Ví dụ:

Input	Output
3 2 6 4 5	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

Ràng buộc:

- \(1\ \leq \ n\ \leq \ 50,000\ \)

- \(1\ \leq \ k\ \leq \ min(n,\ 20)\)

- \(1\ \leq \ a_{i}\ \leq \ 100,000\)

Subtasks:

- 10% điểm: \(n\ \leq \ 10\)

- 10% điểm: \(n\ \leq \ 500,\ k = 1\)

- 10% điểm: \(n \leq 500,\ k \leq \ 2\)

- 20% điểm: \(k = 1\)

- 20% điểm: \(a_{1} = a_{2} = \ldots = a_{n}\)

- 30% điểm: Không có ràng buộc bổ sung