Qua sông

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, \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 đá 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$.

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, \dots, a_K$ ($1 \le a_i \le 10^6$).

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

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