Những Đoạn Nâng Mức · canuc80k4301

Cho dãy số nguyên $a_{1}, a_{2}, \dots, a_{n}$ và mức đích $h$ . Mỗi thao tác chọn một đoạn liên tiếp $[l, r]$ rồi tăng tất cả phần tử trong đoạn đó thêm $1$ .

Bạn cần chọn một tập các đoạn, mỗi đoạn được dùng đúng một lần, sao cho sau khi thực hiện mọi đoạn thì toàn bộ dãy bằng $h$ . Trong tập đã chọn, không được có hai đoạn cùng đầu trái và cũng không được có hai đoạn cùng đầu phải. Hai cách được xem là khác nhau khi tập đoạn khác nhau; tập rỗng được phép.

Input

Dòng đầu chứa $n$ và $h$ .
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .

Output

In số tập đoạn hợp lệ modulo $1 0^{9} + 7$ .

Constraints

$1 \leq n, h \leq 2000$ .
$0 \leq a_{i} \leq 2000$ với mọi $i$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 5$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

2 1
0 0

Output

Giải thích: Có hai tập hợp lệ: chỉ chọn đoạn $[1, 2]$ , hoặc chọn hai đoạn một phần tử $[1, 1]$ và $[2, 2]$ . Cả hai đều đưa dãy thành $(1, 1)$ và không trùng đầu trái hay đầu phải.

Ý tưởng: Quét dãy từ trái sang phải. Trước vị trí i, đặt dp[j] là số cách có j đoạn đang mở và sẽ phủ vị trí i. Tại i có thể mở tối đa một đoạn và đóng tối đa một đoạn vì các đầu trái và đầu phải phải khác nhau.
Ý tưởng: Nếu không mở, cần a_i+j=h; ta hoặc giữ j đoạn, hoặc chọn một trong j đoạn để đóng. Nếu mở, cần a_i+j+1=h; ta hoặc giữ đoạn mới mở, hoặc đóng một trong j+1 đoạn đang tồn tại sau thao tác mở. Sau vị trí cuối phải còn 0 đoạn mở.
Ý tưởng: Mỗi tập đoạn xác định duy nhất quyết định mở và đoạn được đóng ở từng vị trí; chiều ngược lại cũng giữ đúng tính duy nhất đầu mút. Độ phức tạp O(n^2), bộ nhớ O(n).
Lỗi cần tránh: Bỏ sót hoàn toàn trường hợp mở một đoạn mới rồi đóng ngay tại cùng vị trí.
Lỗi cần tránh: Giữ đúng mọi trường hợp biên và kiểu số đã nêu trong đề.
Lỗi cần tránh: Chỉ lấy modulo ở những bài có yêu cầu modulo; bài 10 và bài 9 phải giữ nguyên số nguyên 64 bit.