Bờm có \(N\) thanh gỗ, thanh gỗ \(i\) có độ dài là số nguyên \(l_i\). Bờm muốn dùng một số thanh gỗ trong số này ghép thành một đa giác với các yêu cầu :

• Không cưa cắt hay nối các thanh gỗ
• Đa giác có diện tích dương

Hãy xác định giúp Bờm số cách sử dụng các thanh gỗ, hai cách được coi là khác nhau nếu có một thanh gỗ \(i\) được dùng trong cách này nhưng không được dùng trong cách kia.

Input

• Dòng 1: số nguyên \(N\) \((1 \leq N \leq 4000);\)
• Dòng 2: \(N\) số nguyên \(l_1,l_2,…,l_N\) (\(1 \leq l_i \leq 4000\) ∀i).

Output

• Dòng 1: số nguyên là phần dư khi chia cho \(10^9+7\) của số cách ghép.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 20\); \(l_i \leq 100\).
• Subtask \(2\) (\(40\%\) số điểm): \(n \leq 100\); \(l_i \leq 100\) .
• Subtask \(3\) (\(30\%\) số điểm): \(n, l_i \leq 4000\).

Example

3
10 11 12

1

4
100 1 2 3

0

4
5 5 5 5

5