Score : 1000 points
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:
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).
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).
Input is given from Standard Input in the following format:
N M
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.
2 5
352
Consider the case a = 1, 3, 1, 3, 1 for example.
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.
2020 530
823277409