Câu 4. Qua sông (2.0 điểm)

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ô lên khỏi mặt nước đượ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ờ bên 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, \ldots, 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 đá An nhảy lên ở cách này nhưng không nhảy lên ở cách kia.

Input

Vào từ tệp CAU4.INP gồm:

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

Output

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

Example

5 1
3

3

Scoring

• Có 40% số điểm có \(N \le 20\), \(K = 1\) và \(a = 6\);
• 60% số điểm còn lại có \(N \le 10^5\), \(K \le 10\), \(a_i \le 10^6\).