题目描述

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

• $0$ 以上 $2^N$ 未満の整数からなる、長さ $M$ の数列 $a\ =\ a_1,\ a_2,\ \ldots,\ a_M$ を用意する。

• まずすぬけくんは、以下の操作を好きな回数行う。

  • ある正整数 $d$ を選び、全ての $i~(1\ \leq\ i\ \leq\ M)$ について、$a_i$ を $2$ 進数で表したときの $d$ 桁目（最下位桁は $1$ 桁目とする）を $0$ にする。

• すぬけくんの操作が全て終わったあと高橋くんは、以下の操作を好きな回数行い $a$ を昇順に並べ替えることを目指す。ここで $a$ が昇順であるとは、任意の $i\ ~\ (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}$ をスワップする。

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

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

输入格式

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

$N$ $M$

输出格式

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

题目大意

高桥君和须贺君想出了一个基于数列的游戏。游戏规则如下：

首先准备一个长度为 $M$ 的数列 $a = a_1, a_2, ..., a_M$，其中每个元素都是 $0$ 到 $2^N-1$ 之间的整数。

接下来，须贺君可以任意多次进行以下操作：

选择一个正整数 $d$，并将 $a$ 中每个元素的二进制表示的第 $d$ 位（最低位为第 $1$ 位）设为 $0$。

最终，高桥君可以任意多次进行以下操作，以尝试将 $a$ 排序：

选择相邻的两个元素 $a_i$ 和 $a_{i+1}$，若它们的二进制表示恰好有一位不同，则交换 $a_i$ 和 $a_{i+1}$。 已知存在 $2^{NM}$ 种满足条件的长度为 $M$ 的数列 $a$。其中须贺君无论如何进行操作，高桥君都可以通过合适的交换将 $a$ 排序。请将结果对 $10^9+7$ 取模后输出。

输入格式

输入共一行，包含两个整数 $N$ 和 $M$。

输出格式

输出一个整数，表示可以通过合适的交换将数列 $a$ 排序的数列 $a$ 的数量对 $10^9+7$ 取模后的结果。 翻译贡献：Lord_Sky2048

2 5

352

2020 530

823277409

提示

制約

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

Sample Explanation 1

例えば $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$ つです。