// Use uint64_t to avoid overflow when multiplying
// MODULO * MODULO < UINT64_MAX
constexpr uint64_t MODULO = 1'000'000'007;
static_assert(numeric_limits<uint64_t>::max() / MODULO >= MODULO, "");

uint64_t modulopow(uint64_t x, uint64_t c) {
    x = x % MODULO;
    uint64_t out = 1;
    for (uint64_t i = 0; i < c; ++i) {
        out *= x;
        out %= MODULO;
    }
    return out;
}

uint64_t legoBlocks(int height, int width) {
    vector<uint64_t> row = { 1, 1, 2, 4 };
    for (int i = 4; i <= width; ++i) {
        uint64_t sum = row[i - 1]
                 + row[i - 2]
                 + row[i - 3]
                 + row[i - 4];
        row.push_back(sum % MODULO);
    }

    vector<uint64_t> total;
    for (int i = 0; i <= width; ++i) {
        total.push_back(modulopow(row[i], height));
    }

    vector<uint64_t> stable = {1};
    for (int i = 1; i <= width; ++i) {
        uint64_t unstable = 0;
        for (int j = 1; j < i; ++j) {
            // Avoid double-counting unstable configurations
            unstable += (stable[j] * total[i - j]) % MODULO;
            unstable %= MODULO;
        }
        stable.push_back((total[i] - unstable + MODULO) % MODULO);
    }
    return stable[width];
}