Một ngày nọ Quý phải trông coi cậu em nhỏ a520anhlnb. Vì quá bận nên letangphuquy quăng cho Bảo Anh một túi bự toàn gạch đồ chơi. Các viên gạch chỉ có tối đa 15 loại, mỗi loại có một độ cao khác nhau. Mỗi loại gạch có số lượng vô hạn.

Việc của B.Anh bây giờ là lắp ráp tất cả tòa tháp độ cao \(N\) từ những viên gạch được cho. Gạch chỉ được xếp chồng theo chiều dọc, và mỗi viên gạch được đặt thẳng đứng (theo chiều cao của nó). Hai tòa tháp là khác nhau nếu nếu hai dãy số biểu diễn độ cao của các viên gạch của mỗi tháp là khác nhau.

Bảo anh rất giỏi LEGO và có thể xếp xong một tháp trong chính xác hai phút, bất kể độ cao. Quý muốn biết thời gian cần để cậu em xếp hết các tòa tháp.

Input

• Gồm 3 dòng. Dòng đầu tiên chứa số nguyên \(N\), độ cao của tháp cần xây. Dòng thứ hai chứa số nguyên \(K\), đại diện cho số loại gạch khác nhau trong túi. Dòng thứ ba chứa các số nguyên phân biệt thể hiện độ cao của các viên gạch.

Output

• In ra thời gian (số lượng phút) mà Bảo Anh cần để xây hết mọi tháp có thể. Vì số này có thể rất lớn, hãy in ra kết quả theo modulo \((10^9+7)\)

Constants

• \(1\le N\le 10^{18}\)

• \(1\le k\le 15\)

Các độ cao phân biệt.
Chiều cao của mỗi loại gạch nằm trong đoạn \([1,15]\)

Example

10
1
1

2

5
2
2 3

4

19
2
4 5

8