(Bạn cần đọc đề bài 2 trước khi đọc bài này)
(Các điểm khác nhau giữa bài 2 và bài 3 là giới hạn \(n\), \(a[i]\) và số mod)

Sau khi viết di chúc xong, Canuc80k đã sẵn sàng nhắm mắt. Tiếc là đã qua nhiều thập kỉ, ông vẫn còn sống khỏe. Đến khi tròn 99 tuổi, sau khi nghe đứa cháu ngoại chúc "Chúc ông sống lâu trăm tuổi", ông biết rằng đã đến lúc để viết lại một chiếc di chúc khác. Chỉ có một điểm khác biệt là, những năm qua, ông đã kiếm được thêm rất nhiều mảnh đất nữa. Vì đáp án có thể rất lớn nên cần in ra kết quả sau khi chia lấy dư cho \(10^9 + 7\).

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(n \le 100\)).
• Dòng tiếp theo chứa các số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(a_i \le 20\)).

Output

• Ghi ra một số nguyên duy nhất là đáp án của bài toán sau khi chia lấy dư cho \(10^9 + 7\).

Ràng buộc

• \(30\%\) số lượng test có \(n \le 19\) và tổng tất cả các số trong mảng \(a[]\) không lớn hơn \(200\).
• \(40\%\) số lượng test có tổng tất cả các số trong mảng \(a[]\) không lớn hơn \(200\).
• \(30\%\) số lượng test không giới hạn gì thêm.

Example

3
20 1 1

3