Nhà của An cách trường học một con sông. Giữa dòng sông có \(N\) hòn đá nhỏ xếp thành một hàng và được đánh số thứ tự từ \(1\) đến \(N\) theo hướng từ nhà đến trường.

Mỗi lần đi học, An phải nhảy lên các hòn đá bắt đầu từ hòn đá thứ \(1\) đến hòn đá thứ \(N\) để lên bờ kia. Với mỗi bước nhảy, nếu đang đứng ở hòn đá thứ \(x\), An có thể nhảy đến hòn đá thứ \(x + d\), với \(d\) là ước nguyên dương của một trong \(K\) số nguyên dương \(a_1, a_2, \dots, a_K\).

Một dãy các hòn đá mà An nhảy lên để đi từ hòn đá thứ \(1\) đến hòn đá thứ \(N\) gọi là một cách đi. Hai cách đi khác nhau nếu tồn tại một hòn đá mà An nhảy lên ở cách này nhưng không nhảy lên ở cách kia.

Yêu cầu: Hãy đếm số cách đi khác nhau mà An có thể thực hiện để đi từ hòn đá thứ \(1\) đến hòn đá thứ \(N\).

Input

• Dòng đầu tiên ghi hai số nguyên dương \(N, K\).
• Dòng thứ hai ghi \(K\) số \(a_1, a_2, \dots, a_K\) (\(1 \le a_i \le 10^6\)).

Output

• Ghi ra một số duy nhất là số cách khác nhau mà An có thể thực hiện được sau khi chia lấy dư cho \(10^9 + 7\).

Example

5 1
3

3

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(N \le 20, K = 1\) và \(a_1 = 6\).
• Subtask \(2\) (\(60\%\) số điểm): \(N \le 10^5, K \le 10, a_i \le 10^6\) (với mọi \(i = 1, \dots, K\)).