Sắp xếp phòng ở

Trong một dự án chung cư mới, FullHouse Dev được giao nhiệm vụ sắp xếp chỗ ở cho cư dân. Tòa nhà có \(M\) tầng, mỗi tầng có vô số phòng giống hệt nhau. Đặc biệt, mỗi phòng ở tầng khác nhau sẽ có sức chứa khác nhau, trong khi các phòng cùng tầng có sức chứa giống nhau.

Bài toán

FullHouse Dev cần sắp xếp chỗ ở cho \(N\) cư dân giống nhau. Mỗi phòng ở tầng thứ \(i\) phải chứa đúng \(i\) người (không được nhiều hơn hay ít hơn). Nhóm cần tính toán số cách sắp xếp khác nhau để bố trí chỗ ở cho tất cả cư dân.

Cách sắp xếp được tính như sau: Ví dụ có 5 người và 3 tầng, trong đó tầng 1 có sức chứa 1 người và tầng 2 có sức chứa 2 người:

• (1,2,2) là một cách sắp xếp, nghĩa là 1 người ở tầng 1, 4 người còn lại ở hai phòng tầng 2 (mỗi phòng 2 người).
• (1,2,2), (2,1,2), (2,2,1) được tính là cùng một cách sắp xếp vì không phân biệt thứ tự.

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(M\) và \(N\), lần lượt là số tầng và số người.
• Dòng thứ hai chứa \(M\) số nguyên, số thứ \(i\) biểu thị sức chứa của mỗi phòng ở tầng \(i\).

OUTPUT FORMAT:

• In ra số cách sắp xếp khác nhau, lấy phần dư cho \(10^9 + 7\).

Ràng buộc:

• \(1 \leq M \leq 50\)
• \(1 \leq N \leq 50\)
• Tất cả sức chứa đều khác nhau

Ví dụ

INPUT

3 5
1 2 3

OUTPUT

5

Giải thích

Có 5 cách sắp xếp khác nhau:

1. (1,1,1,1,1): 5 người ở 5 phòng tầng 1
2. (1,1,1,2): 3 người ở 3 phòng tầng 1, 2 người ở 1 phòng tầng 2
3. (1,1,3): 2 người ở 2 phòng tầng 1, 3 người ở 1 phòng tầng 3
4. (1,2,2): 1 người ở tầng 1, 4 người ở 2 phòng tầng 2
5. (2,3): 2 người ở 1 phòng tầng 2, 3 người ở 1 phòng tầng 3