Mientras visita el mercado de agricultores, Busy Beaver se detiene a observar a un mago callejero. El mago presenta una fila de $N$ cajas, que contienen enteros no negativos de $M$ bits $a_1, a_2, \dots, a_N$, donde $0 \le a_i < 2^M$ para todo $1 \le i \le N$.
El mago ordena mágicamente las cajas en orden no decreciente mediante una serie de intercambios mágicos. En un solo intercambio mágico, el mago elige un índice $i$ ($1 \le i < N$) tal que las representaciones binarias de $a_i$ y $a_{i+1}$ difieran exactamente en un bit, e intercambia $a_i$ y $a_{i+1}$.
Observando la actuación, Busy Beaver se pregunta acerca de los límites de este truco. De todos los $2^{MN}$ valores iniciales posibles de $a_1, a_2, \dots, a_N$ en las cajas, ¿cuántos de ellos pueden ordenarse en orden no decreciente usando intercambios mágicos? Dado que este número puede ser grande, Busy Beaver se conforma con encontrarlo módulo $10^9 + 7$.
Entrada
La primera y única línea de la entrada contiene dos enteros $N$ y $M$ ($1 \le N, M \le 50$).
Salida
Imprima un solo entero: el número de secuencias que pueden ordenarse usando intercambios mágicos, módulo $10^9 + 7$.
Subtareas
Hay cinco subtareas para este problema:
- (10 puntos): $1 \le N, M \le 5$.
- (20 puntos): $1 \le M \le 4$.
- (10 puntos): $1 \le M \le 10$.
- (10 puntos): $1 \le M \le 15$.
- (50 puntos): Sin restricciones adicionales.
Ejemplos
Entrada 1
3 2
Salida 1
44
Entrada 2
50 1
Salida 2
898961331
Entrada 3
10 10
Salida 3
649370314
Nota
En el primer ejemplo, una secuencia que puede ordenarse usando intercambios mágicos es $[a_1, a_2, a_3] = [3, 1, 2]$, de la siguiente manera:
- Elija $i = 1$. Note que $a_1 = 3$ y $a_2 = 1$ difieren exactamente en un bit, por lo que este es un intercambio mágico. La secuencia se convierte en $[1, 3, 2]$.
- Elija $i = 2$. Note que $a_2 = 3$ y $a_3 = 2$ difieren exactamente en un bit, por lo que este es un intercambio mágico. La secuencia se convierte en $[1, 2, 3]$, la cual está en orden no decreciente.
De las $2^{3 \cdot 2} = 64$ secuencias iniciales, 44 de ellas pueden ordenarse usando intercambios mágicos.