Trong hội thi DH và ĐBBB 2017 có tổ chức cho các thí sinh trò chơi lắp ghép như sau: Cho \(K\) loại khối gỗ, mỗi khối gỗ không hạn chế số lượng và có chiều cao tương ứng là \(H_1, H_2, ..., H_k\), dùng các khối gỗ này sếp chồng lên nhau để đạt đúng độ cao \(N\). Mỗi thí sinh tham gia trò chơi là tìm số cách sắp xếp khác nhau từ các khối gỗ để đạt đúng độ cao \(N\).

Yêu cầu: Cho \(N\) và chiều cao của mỗi loại khối gỗ, tìm số cách xếp từ các khối gỗ để đạt độ cao \(N\).

Input

• Dòng 1 ghi 2 số nguyên dương \(N\) và \(K\).
• Dòng 2 ghi \(K\) số \(H_1, H_2, ..., H_k\), các số khác nhau từng đôi một.

Output

• Ghi ra một số nguyên là số cách xếp gỗ, vì số cách rất lớn nên lấy kết quả là phần dư của \(10^9+7\).

Constraints

• \(K\le N \le 10^5, K\le 1000\)
• \(0 < H_i \le N\)

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(K < N \le 10, 0 < H_i \le N\)
• Subtask \(2\) (\(30\%\) số điểm): \(N \le 10^4, K = 3\) và độ cao tương ứng là \(1, 2\) và \(3\), \(0 < H_i \le N\)
• Subtask \(3\) (\(40\%\) số điểm): \(N \le 10^5\), \(3 < K \le 1000\) và \(0 < H_i \le N\)

Example

3 2
1 2 

3