Problem: 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.

Examples

Input

2 5


Output

352


Input

2020 530


Output

823277409

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;

class Modular {
private:
    static long long MOD;
    // a * x + b * y == g; g == gcd(x, y)
    static void extended_gcd(long long x, long long y, long long& a, long long& b, long long& g) {
        if (x < 0) {
            extended_gcd(-x, y, a, b, g);
            a = -a;
        } else if (y < 0) {
            extended_gcd(x, -y, a, b, g);
            b = -b;
        } else if (x > y) {
            extended_gcd(y, x, b, a, g);
        } else if (x == 0) {
            a = 0;
            b = 1;
            g = y;
        } else {
            long long a1 = -1;
            long long b1 = -1;
            extended_gcd(y % x, x, a1, b1, g);
            b = a1;
            a = b1 - a1 * (y / x);
        }
    }
    static long long mod_inv(long long x, long long m) {
        long long a = 0;
        long long b = 0;
        long long g = 0;
        extended_gcd(x, m, a, b, g);
        a = ((a % m) + m) % m;
        return a;
    }
public:
    long long value;
    Modular(): value(0) {}
    explicit Modular(long long v): value(normalize(v)) {}
    static long long normalize(long long v) {
        v = v % MOD;
        if (v < 0)
            v += MOD;
        return v;
    }

    bool operator==(const Modular& a) const {return value == a.value;}
    bool operator<(const Modular& a) const { return value < a.value;}
    Modular operator+=(const Modular& a) {value = normalize(value + a.value); return *this;}
    Modular operator-=(const Modular& a) {value = normalize(value - a.value); return *this;}
    Modular operator*=(const Modular& a) {value = normalize(value * a.value); return *this;}
    Modular operator/=(const Modular& a) {return (*this) *= a.inv();}

    Modular operator++() {value = normalize(value + 1); return *this;}
    Modular operator--() {value = normalize(value - 1); return *this;}
    Modular operator++(int) {Modular tmp = *this; value = normalize(value + 1); return tmp;}
    Modular operator--(int) {Modular tmp = *this; value = normalize(value - 1); return tmp;}

    template <typename T>
    Modular operator+=(const T& a) {value = normalize(value + a); return *this;}
    template <typename T>
    Modular operator-=(const T& a) {value = normalize(value - a); return *this;}
    template <typename T>
    Modular operator*=(const T& a) {value = normalize(value * a); return *this;}

    Modular inv() const {return Modular(mod_inv(value, MOD));}
    Modular pow(long long p) const {  // this doesn't assume prime MOD
        Modular res(1);
        Modular sq(value);
        while (p > 0) {
            if (p % 2 == 1) {
                res *= sq;
            }
            sq *= sq;
            p /= 2;
        }
        return res;
    }

    static void set_mod(long long mod) {MOD = mod;}
};
long long Modular::MOD = 0;

Modular operator+(const Modular& a, const Modular& b) {Modular c(a); return c += b;}
template<typename T>
Modular operator+(const Modular& a, const T& b) {return a + Modular(b);}
template<typename T>
Modular operator+(const T& a, const Modular& b) {return Modular(a) + b;}

Modular operator-(const Modular& a, const Modular& b) {Modular c(a); return c -= b;}
template<typename T>
Modular operator-(const Modular& a, const T& b) {return a - Modular(b);}
template<typename T>
Modular operator-(const T& a, const Modular& b) {return Modular(a) - b;}

Modular operator*(const Modular& a, const Modular& b) {Modular c(a); return c *= b;}
template<typename T>
Modular operator*(const Modular& a, const T& b) {return a * Modular(b);}
template<typename T>
Modular operator*(const T& a, const Modular& b) {return Modular(a) * b;}

Modular operator/(const Modular& a, const Modular& b) {Modular c(a); return c /= b;}
template<typename T>
Modular operator/(const Modular& a, const T& b) {return a / Modular(b);}
template<typename T>
Modular operator/(const T& a, const Modular& b) {return Modular(a) / b;}

std::ostream& operator<<(std::ostream& os, const Modular& m) {
    return os << m.value;
}

std::istream& operator>>(std::istream& is, Modular& m) {
    return is >> m.value;
}
int main() {
    Modular::set_mod(1000000007);
    int n, m;
    cin >> n >> m;
    vector<vector<Modular>> dp(n + 1, vector<Modular>(m + 1));
    for (int i = 0; i <= m; ++i) {
        dp[0][i] = Modular(1);
        if (i == 0)
            dp[1][i] = Modular(1);
        else
            dp[1][i] = 2 * dp[1][i - 1];
    }
    Modular two(2);
    vector<Modular> twos(m + 1);
    twos[0] = Modular(1);
    for (int i = 1; i <= m; ++i)
        twos[i] = 2 * twos[i - 1];
    vector<Modular> itwos(m + 1);
    itwos[0] = Modular(1);
    for (int i = 1; i <= m; ++i)
        itwos[i] = itwos[i - 1] / 2;


    for (int i = 2; i <= n; ++i) {
        Modular s;
        for (int j = 0; j <= m; ++j) {
            dp[i][j] = (j + 1) * dp[i - 1][j];
//            for (int p = 2; p <= j; ++p) {
//                dp[i][j] += two.pow(p - 2) * (j - p + 1) * dp[i - 1][j - p + 1];
//            }
            if (j >= 2)
                s += ((j - 1) * dp[i - 1][j - 1]) * itwos[j];
            dp[i][j] += s * twos[j];
        }
    }
    cout << dp[n][m] << "\n";
    return 0;
}