Do hạn hán, cỏ trên đồng của Nông dân John đã khô héo. Sau nhiều giờ tuyệt vọng và suy ngẫm, FJ nảy ra ý tưởng tuyệt vời là mua ngô để cho những chú bò quý giá của mình ăn.

\(N\) chú bò của FJ (\(1\le N\le 100\)) xếp thành một hàng, trong đó chú bò thứ \(i\) có mức đói là số nguyên không âm \(h_i\). Vì bò của FJ là động vật có tính xã hội và nhất quyết ăn cùng nhau, cách duy nhất để FJ giảm mức đói của đàn bò là chọn hai chú bò kề nhau \(i\) và \(i+1\), rồi cho mỗi con một túi ngô, khiến mức đói của mỗi con giảm đi một.

FJ muốn cho bò ăn đến khi tất cả có cùng một mức đói không âm. Mặc dù không biết chính xác mức đói của đàn bò, ông biết một cận trên cho mức đói của mỗi con; cụ thể, mức đói \(h_i\) của chú bò thứ \(i\) không vượt quá \(H_i\) (\(0\le H_i\le 1000\)).

Nhiệm vụ của bạn là đếm số bộ \(N\) mức đói \([h_1,h_2,\ldots,h_N]\) phù hợp với các cận trên này mà FJ có thể đạt được mục tiêu, lấy modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu chứa \(N\).

Dòng thứ hai chứa \(H_1,H_2,\ldots,H_N\).

Dữ liệu ra

In số bộ \(N\) mức đói, lấy modulo \(10^9+7\).

Phân nhóm

\(N\) chẵn trong các test mang số chẵn và lẻ trong các test mang số lẻ.

• Các test 3 và 4 thỏa mãn \(N\le 6\) và \(H_i\le 10\).
• Các test 5 đến 10 thỏa mãn \(N\le 50\) và \(H_i\le 100\).
• Các test 11 đến 20 không có thêm ràng buộc.

Ví dụ

3
9 11 7

241

4
6 8 5 9

137

Nguồn

USACO 2022 January Contest, Gold — Drought: https://usaco.org/index.php?page=viewproblem2&cpid=1185

Tác giả: Arpan Banerjee và Benjamin Qi.