Một dãy số ~a_1, a_2, ..., a_n~ (~n \ge 4~) được gọi là dãy đặc biệt nếu đồng thời thỏa mãn hai điều kiện sau:

• ~n~ chẵn.
• ~a_1 + a_n > a_2 + a_{n-1}~ ~> ... > a_{\frac{n}{2}} + a_{\frac{n}{2} + 1}~.

Yêu cầu: Cho dãy số gồm ~m~ phần tử, bao gồm các số ~a_1, a_2, ..., a_m~ (~4 \le m \le 350~). Nhiệm vụ của bạn là hãy đếm số lượng dãy con đã cho thỏa mãn dãy đặc biệt theo định nghĩa trên. Biết rằng, ~a_{i_1}, a_{i_2}, ..., a_{i_k}~ là một dãy con nếu tồn tại dãy chỉ số ~i_1 < i_2 < ... i_k~ với (~i_1, i_2..., i_k \in [1; m]~).

INPUT

Dòng đầu tiên chứa số nguyên dương ~m~ (~4 \le m \le 350~).

Dòng tiếp theo chứa ~m~ số nguyên dương ~a_i~ (~1 \le a_i \le 500~).

OUTPUT

In ra số nguyên duy nhất là số lượng dãy con đặc biệt khi chia dư cho ~10^9 + 9~.

SAMPLE INPUT

6
1 8 4 9 7 5

SAMPLE OUTPUT

2

Có hai dãy đặc biệt là ~{8, 4, 9, 7}~ và ~{8, 4, 7, 5}~.

SUBTASKS