農産物直売所を訪れた Busy Beaver は、大道芸人の手品を見ようと足を止めました。大道芸人は $N$ 個の箱を一列に並べ、それぞれに $M$ ビットの非負整数 $a_1, a_2, \dots, a_N$ を入れています。ここで、すべての $1 \le i \le N$ に対して $0 \le a_i < 2^M$ です。

大道芸人は「魔法の入れ替え」を繰り返すことで、箱を非減少順に並べ替えます。1 回の魔法の入れ替えでは、大道芸人は $a_i$ と $a_{i+1}$ の二進数表現がちょうど 1 ビットだけ異なるようなインデックス $i$ ($1 \le i < N$) を選び、$a_i$ と $a_{i+1}$ を入れ替えます。

このパフォーマンスを見ていた Busy Beaver は、この手品の限界について疑問を持ちました。箱の中の $a_1, a_2, \dots, a_N$ の初期値として考えられるすべての $2^{MN}$ 通りの組み合わせのうち、魔法の入れ替えを用いて非減少順に並べ替えることができるものはいくつあるでしょうか？ この数は非常に大きくなる可能性があるため、Busy Beaver はその数を $10^9 + 7$ で割った余りを求めることにしました。

入力

入力は以下の形式で与えられます。

$N$ $M$

ここで、$1 \le N, M \le 50$ です。

出力

魔法の入れ替えを用いて並べ替えることができる数列の個数を $10^9 + 7$ で割った余りを 1 つの整数で出力してください。

小課題

この問題には 5 つの小課題があります。

• (10 点): $1 \le N, M \le 5$
• (20 点): $1 \le M \le 4$
• (10 点): $1 \le M \le 10$
• (10 点): $1 \le M \le 15$
• (50 点): 追加の制約はありません。

入出力例

入力 1

3 2

出力 1

44

入力 2

50 1

出力 2

898961331

入力 3

10 10

出力 3

649370314

注記

最初の例において、魔法の入れ替えで並べ替え可能な数列の 1 つは $[a_1, a_2, a_3] = [3, 1, 2]$ であり、以下のように並べ替えられます。

1. $i = 1$ を選びます。$a_1 = 3$ と $a_2 = 1$ は二進数表現でちょうど 1 ビットだけ異なるため、これは魔法の入れ替えです。数列は $[1, 3, 2]$ となります。
2. $i = 2$ を選びます。$a_2 = 3$ と $a_3 = 2$ は二進数表現でちょうど 1 ビットだけ異なるため、これは魔法の入れ替えです。数列は $[1, 2, 3]$ となり、非減少順になります。

考えられる $2^{3 \cdot 2} = 64$ 通りの初期数列のうち、44 通りが魔法の入れ替えで並べ替え可能です。