Cho \(m\) cái hộp được chia vào \(n\) dãy hộp, dãy thứ \(i\) gồm \(a_{i}\) cái hộp có màu \(i\) và được đánh số thứ tự từ \(1\) đến \(a_{i}\).

Mỗi một bước, ta có thể chọn \(2\) hộp \(x\) và \(y\) lần lượt thuộc dãy hộp \(i\) và \(j\) \((1 \leq x \leq a_{i}, 1 \leq y \leq a_{j})\) và đổi vị trí \(2\) cái hộp đó.

Sau một số bước, các dãy hộp phải thỏa mãn điều kiện với \(1 \leq i \leq n\), dãy thứ \(i\) không được chứa bất kì cái hộp nào có màu \(i\).

Hỏi có bao nhiêu cách sắp xếp khác nhau của những dãy hộp biết \(2\) cách sắp xếp được xem là khác nhau nếu tồn tại \(u\) và \(v\) \((1 \leq v \leq n, 1 \leq u \leq a_{v})\) sao cho cái hộp thứ \(u\) của dãy thứ \(v\) của 2 cách sắp xếp đó khác màu hoặc khác số thứ tự.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n\) và \(m\) \((2 \leq n \leq 500, 2 \leq m \leq 1000)\).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq m)\).
• Dữ liệu vào luôn đảm bảo \(\sum_{i = 1}^n{a_{i}} = m\).

Output

• In ra một số duy nhất là kết quả của bài toán modulo \(998244353\).

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(n, m \leq 10\).
• Subtask \(2\) (\(20\%\) số điểm): \(n, m \leq 20\).
• Subtask \(3\) (\(20\%\) số điểm): \(a_{i} = 1\) với \(1 \leq i \leq n\).
• Subtask \(4\) (\(15\%\) số điểm): \(a_{i} = 2\) với \(1 \leq i \leq n\).
• Subtask \(5\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 4
1 1 2

4

3 5
1 2 2

16