Có \(k\) loại bước nhảy: \(b_1, b_2, \dots, b_k\) bậc. Đếm số cách leo hết \(n\) bậc (có thứ tự). Modulo \(10^9+7\).

Định dạng đầu vào

• Dòng đầu: \(n, k\) (\(1 \le n \le 10^{18}\), \(1 \le k \le 10\)).
• Dòng hai: \(k\) số \(b_i\) (\(1 \le b_i \le 10\)).

Định dạng đầu ra

• Một số nguyên là kết quả.

Ví dụ

Input:

10 2
1 2

Output:

89

Ràng buộc

• 100% số điểm: \(k \le 10\), \(b_i \le 10\).