/ 
実行時間制限: 3 sec / メモリ制限: 1024 MB
配点 : 1000 点
問題文
高橋くんとすぬけくんは、数列を使った次のようなゲームを思いつきました。
-
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 で割った余りを求めてください。
制約
- 入力は全て整数である。
- 1 \leq N \leq 5000
- 2 \leq M \leq 5000
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
ゲームで使ったとき、すぬけくんがどのように操作を行ったとしても、高橋くんが適当な操作を行うことで昇順に並べ替えることができる数列の個数を 10^9 + 7 で割った余りを出力せよ。
入力例 1
2 5
出力例 1
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 つです。
入力例 2
2020 530
出力例 2
823277409
Score : 1000 points
Problem Statement
Takahashi and Snuke came up with a game that uses a number sequence, as follows:
-
Prepare a sequence of length M consisting of integers between 0 and 2^N-1 (inclusive): a = a_1, a_2, \ldots, a_M.
-
Snuke first does the operation below as many times as he likes:
- Choose a positive integer d, and for each i (1 \leq i \leq M), in binary, set the d-th least significant bit of a_i to 0. (Here the least significant bit is considered the 1-st least significant bit.)
-
After Snuke finishes doing operations, Takahashi tries to sort a in ascending order by doing the operation below some number of times. Here a is said to be in ascending order when a_i \leq a_{i + 1} for all i (1 \leq i \leq M - 1).
- Choose two adjacent elements of a: a_i and a_{i + 1}. If, in binary, these numbers differ in exactly one bit, swap a_i and a_{i + 1}.
There are 2^{NM} different sequences of length M consisting of integers between 0 and 2^N-1 that can be used in the game.
How many among them have the following property: if used in the game, there is always a way for Takahashi to sort the sequence in ascending order regardless of Snuke's operations? Find the count modulo (10^9 + 7).
Constraints
- All values in input are integers.
- 1 \leq N \leq 5000
- 2 \leq M \leq 5000
Input
Input is given from Standard Input in the following format:
N M
Output
Print the number, modulo (10^9 + 7), of sequences with the property: if used in the game, there is always a way for Takahashi to sort the sequence in ascending order regardless of Snuke's operations.
Sample Input 1
2 5
Sample Output 1
352
Consider the case a = 1, 3, 1, 3, 1 for example.
- When the least significant bit of each element of a is set to 0, a = 0, 2, 0, 2, 0;
- When the second least significant bit of each element of a is set to 0, a = 1, 1, 1, 1, 1;
- When the least two significant bits of each element of a are set to 0, a = 0, 0, 0, 0, 0.
In all of the cases above and the case when Snuke does no operation to change a, we can sort the sequence by repeatedly swapping adjacent elements that differ in exactly one bit. Thus, this sequence has the property: if used in the game, there is always a way for Takahashi to sort the sequence in ascending order regardless of Snuke's operations.
Sample Input 2
2020 530
Sample Output 2
823277409