配点 : $1000$ 点

問題文

高橋くんとすぬけくんは、数列を使った次のようなゲームを思いつきました。

• $0$ 以上 $2^N$ 未満の整数からなる、長さ $M$ の数列 $a = a_1, a_2, \ldots, a_M$ を用意する。
• まずすぬけくんは、以下の操作を好きな回数行う。
  • ある正整数 $d$ を選び、全ての $i \sim (1 \leq i \leq M)$ について、$a_i$ を $2$ 進数で表したときの $d$ 桁目（最下位桁は $1$ 桁目とする）を $0$ にする。
• ある正整数 $d$ を選び、全ての $i \sim (1 \leq i \leq M)$ について、$a_i$ を $2$ 進数で表したときの $d$ 桁目（最下位桁は $1$ 桁目とする）を $0$ にする。
• すぬけくんの操作が全て終わったあと高橋くんは、以下の操作を好きな回数行い $a$ を昇順に並べ替えることを目指す。ここで $a$ が昇順であるとは、任意の $i \sim (1 \leq i \leq M - 1)$ について $a_i \leq a_{i + 1}$ であることを言う。
  • $a$ の隣接する $2$ 要素 $a_i, a_{i + 1}$ を選び、$a_i, a_{i + 1}$ を $2$ 進数で表したときちょうど $1$ 桁が異なる場合、$a_i, a_{i + 1}$ をスワップする。
• $a$ の隣接する $2$ 要素 $a_i, a_{i + 1}$ を選び、$a_i, a_{i + 1}$ を $2$ 進数で表したときちょうど $1$ 桁が異なる場合、$a_i, a_{i + 1}$ をスワップする。

ゲームで使うことができる、$0$ 以上 $2^N$ 未満の整数からなる、長さ $M$ の数列は $2^{NM}$ 個存在します。

このうちゲームで使ったとき、すぬけくんがどのように操作を行ったとしても、高橋くんが適当な操作を行うことで昇順に並べ替えることができるものは何個あるでしょうか。 $10^9 + 7$ で割った余りを求めてください。

制約

• 入力は全て整数である。
• $1 \leq N \leq 5000$
• $2 \leq M \leq 5000$

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

出力

ゲームで使ったとき、すぬけくんがどのように操作を行ったとしても、高橋くんが適当な操作を行うことで昇順に並べ替えることができる数列の個数を $10^9 + 7$ で割った余りを出力せよ。

2 5

352

例えば $a = 1, 3, 1, 3, 1$ の場合を考えます。このとき、

• $a$ の各要素の $1$ 桁目を $0$ にすると $a = 0, 2, 0, 2, 0$ に、
• $a$ の各要素の $2$ 桁目を $0$ にすると $a = 1, 1, 1, 1, 1$ に、
• $a$ の各要素の $1, 2$ 桁目を $0$ にすると $a = 0, 0, 0, 0, 0$ に、

なります。 すぬけくんが操作を行わず $a$ が変わらない場合も含めて、いずれの場合も、$2$ 進数でちょうど $1$ 桁が異なる隣接要素のスワップを繰り返して、昇順に並び替えることができます。 よってこの数列は、ゲームで使ったとき、すぬけくんがどのように操作を行っても高橋くんが適当な操作を行うことで昇順に並べ替えることができる数列の $1$ つです。

2020 530

823277409