Loli là một nhân viên của tập đoàn khét tiếng Anh Em Rọt. Mặc dù công ty có lợi nhuận hàng chục tỷ một tháng, nhưng do ăn chia không đồng đều, nên ác cảm của Loli đối với công ty càng ngày càng ác liệt. Để trả mối tư thù, Loli quyết định sẽ tố cáo công ty bán thực phẩm chức năng giả!

Mặt hàng bán chạy nhất của công ty chính là Kẹo rau Kehahaha. Để lật tẩy trò lừa đảo này, trước hết Loli sẽ cần những tài liệu liên quan tới sản phẩm trên. Qua tìm hiểu, Loli biết được tài liệu này đã được mã hóa bằng một con số đặc biệt, đó là Số số nguyên dương thỏa mãn điều kiện sau:

• Số nguyên dương này dài không quá ~n~ chữ số;

• Số này không có chữ số ~0~ ở đầu;

• Chữ số thứ ~i\ (0\le i\le 9)~ phải xuất hiện ít nhất ~a_i~ lần.

Vì số lượng có thể rất lớn, dãy số cuối cùng sẽ là phần dư của kết quả khi chia cho ~10^9+7~. Như vậy, để giải mã, Loli cần biết chính xác số lượng số thỏa mãn điều kiện trên. Bạn hãy giúp Loli nhé!

Input

• Dòng đầu chứa số nguyên ~n\ (1\le n \le 100)~;

• Dòng thứ hai chứa ~10~ số nguyên ~a_i\ (0\le a_i\le n)~, ứng với các chữ số từ ~0~ đến ~9~.

Output

Một dòng chứa một số nguyên là phần dư kết quả khi chia cho ~10^9+7~.

Scoring

• Subtask 1 (40%): ~n\le 6~;

• Subtask 2 (40%): ~a_i \le 1~;

• Subtask 3 (20%): Không có ràng buộc gì thêm.

Sample Input 1

2
0 1 0 0 0 0 0 0 0 0

Sample Output 1

19

Sample Input 2

3
1 0 0 0 0 1 0 0 0 0

Sample Output 2

36

Notes

Ở ví dụ thứ nhất, dễ thấy chỉ có 19 số thỏa mãn, đó là số ~1~, các số từ ~10~ tới ~19~, và ~21~, ~31~, ..., ~91~.