Trong khi ghé thăm chợ nông sản, Busy Beaver dừng lại xem một ảo thuật gia đường phố. Ảo thuật gia trình diễn một hàng gồm $N$ chiếc hộp, chứa các số nguyên không âm có $M$ bit $a_1, a_2, \dots, a_N$, trong đó $0 \le a_i < 2^M$ với mọi $1 \le i \le N$.
Ảo thuật gia sắp xếp các chiếc hộp theo thứ tự không giảm bằng một loạt các phép hoán đổi kỳ diệu. Trong một phép hoán đổi kỳ diệu, ảo thuật gia chọn một chỉ số $i$ ($1 \le i < N$) sao cho biểu diễn nhị phân của $a_i$ và $a_{i+1}$ khác nhau đúng một bit, sau đó hoán đổi $a_i$ và $a_{i+1}$.
Theo dõi màn trình diễn, Busy Beaver tự hỏi về giới hạn của trò ảo thuật này. Trong số tất cả $2^{MN}$ giá trị khởi tạo có thể có của $a_1, a_2, \dots, a_N$ trong các chiếc hộp, có bao nhiêu giá trị có thể được sắp xếp theo thứ tự không giảm bằng cách sử dụng các phép hoán đổi kỳ diệu? Vì con số này có thể rất lớn, Busy Beaver chỉ cần tìm kết quả theo modulo $10^9 + 7$.
Dữ liệu vào
Dòng đầu tiên và duy nhất chứa hai số nguyên $N$ và $M$ ($1 \le N, M \le 50$).
Dữ liệu ra
In ra một số nguyên duy nhất: số lượng các dãy có thể được sắp xếp bằng các phép hoán đổi kỳ diệu, theo modulo $10^9 + 7$.
Nhiệm vụ con
Có năm nhiệm vụ con cho bài toán này:
- (10 điểm): $1 \le N, M \le 5$.
- (20 điểm): $1 \le M \le 4$.
- (10 điểm): $1 \le M \le 10$.
- (10 điểm): $1 \le M \le 15$.
- (50 điểm): Không có ràng buộc bổ sung.
Ví dụ
Dữ liệu vào 1
3 2
Dữ liệu ra 1
44
Dữ liệu vào 2
50 1
Dữ liệu ra 2
898961331
Dữ liệu vào 3
10 10
Dữ liệu ra 3
649370314
Ghi chú
Trong ví dụ đầu tiên, một dãy có thể được sắp xếp bằng các phép hoán đổi kỳ diệu là $[a_1, a_2, a_3] = [3, 1, 2]$, như sau:
- Chọn $i = 1$. Lưu ý rằng $a_1 = 3$ và $a_2 = 1$ khác nhau đúng một bit, vì vậy đây là một phép hoán đổi kỳ diệu. Dãy trở thành $[1, 3, 2]$.
- Chọn $i = 2$. Lưu ý rằng $a_2 = 3$ và $a_3 = 2$ khác nhau đúng một bit, vì vậy đây là một phép hoán đổi kỳ diệu. Dãy trở thành $[1, 2, 3]$, đây là thứ tự không giảm.
Trong tổng số $2^{3 \cdot 2} = 64$ dãy khởi tạo, có 44 dãy có thể được sắp xếp bằng các phép hoán đổi kỳ diệu.