En visitant le marché fermier, Busy Beaver s'arrête pour regarder un magicien de rue. Le magicien présente une rangée de $N$ boîtes, contenant des entiers non négatifs de $M$ bits $a_1, a_2, \dots, a_N$, où $0 \le a_i < 2^M$ pour tout $1 \le i \le N$.

Le magicien trie magiquement les boîtes dans un ordre non décroissant par une série d'échanges magiques. Lors d'un seul échange magique, le magicien choisit un indice $i$ ($1 \le i < N$) tel que les représentations binaires de $a_i$ et $a_{i+1}$ diffèrent par exactement un bit, et échange $a_i$ et $a_{i+1}$.

En observant la performance, Busy Beaver s'interroge sur les limites de ce tour. Parmi toutes les $2^{MN}$ valeurs initiales possibles de $a_1, a_2, \dots, a_N$ dans les boîtes, combien d'entre elles peuvent être triées dans un ordre non décroissant en utilisant des échanges magiques ? Comme ce nombre peut être grand, Busy Beaver se contente de le trouver modulo $10^9 + 7$.

Entrée

La première et unique ligne de l'entrée contient deux entiers $N$ et $M$ ($1 \le N, M \le 50$).

Sortie

Affichez un seul entier : le nombre de séquences qui peuvent être triées en utilisant des échanges magiques, modulo $10^9 + 7$.

Sous-tâches

Il y a cinq sous-tâches pour ce problème :

• (10 points) : $1 \le N, M \le 5$.
• (20 points) : $1 \le M \le 4$.
• (10 points) : $1 \le M \le 10$.
• (10 points) : $1 \le M \le 15$.
• (50 points) : Aucune contrainte supplémentaire.

Exemples

Entrée 1

3 2

Sortie 1

44

Entrée 2

50 1

Sortie 2

898961331

Entrée 3

10 10

Sortie 3

649370314

Remarque

Dans le premier exemple, une séquence qui peut être triée en utilisant des échanges magiques est $[a_1, a_2, a_3] = [3, 1, 2]$, comme suit :

1. Choisir $i = 1$. Notez que $a_1 = 3$ et $a_2 = 1$ diffèrent par exactement un bit, il s'agit donc d'un échange magique. La séquence devient $[1, 3, 2]$.
2. Choisir $i = 2$. Notez que $a_2 = 3$ et $a_3 = 2$ diffèrent par exactement un bit, il s'agit donc d'un échange magique. La séquence devient $[1, 2, 3]$, qui est dans un ordre non décroissant.

Sur les $2^{3 \cdot 2} = 64$ séquences initiales, 44 d'entre elles peuvent être triées en utilisant des échanges magiques.