// 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];
}

def legoBlocks(n, m):

    # Step 1: O(W)       
    ## Four base cases (widths 0-3) for row walls
    row_combinations = [1, 1, 2, 4]
    
    # Build row combinations up to current wall's width
    while len(row_combinations) <= m: 
        row_combinations.append(sum(row_combinations[-4:]))
    
    # Compute total combinations 
    # for constructing a wall of height N of varying widths
    total = [pow(c, n) for c in row_combinations]
    
    # Step 3: O(W^2)
    # Find the number of unstable wall configurations 
    # for a wall of height N of varying widths
    unstable = [0, 0]
    
    # Divide the wall into left part and right part,
    # and calculate the combination of left part and right part.
    # From width is 2, we start to consider about violations
    for i in range(2, m + 1):
        # i: current total width, j: left width, i - j: right width
        # f: (left part - previous vertical violation)*right part
				# result = sum of f applied to all 1-i
				
        f = lambda j: (total[j] - unstable[j]) * total[i - j]
        result = sum(map(f, range(1, i)))
        unstable.append(result)
    
    return (total[m] - unstable[m])

def legoBlocks(n, m):
    f = [1]
    g = [1]
    h = [1]
    for i in range(1, m + 1):
        sumhg = 0
        for j in range(1, i):
            sumhg += h[j] * g[i-j] % (10**9+7)
        f.append(sum(f[-4:]) % (10**9+7))    
        g.append(f[i] ** n % (10**9+7))
        h.append((g[i] - sumhg) % (10**9+7))
    return h[-1] % (10**9+7)

class Result {

    public static long modBig(long i, long MOD) {
        long res = i % MOD;
        if (res < 0) {
            res += MOD;
        }
        return res;
    }
    
    //Right-to-left binary method from Wiki
    public static long modPow(long i, int pow, long MOD) {
        if (MOD == 1) {
            return 0;
        }
        
        long res = 1;
        i = i % MOD;
        
        while (pow > 0) {
            if (pow % 2 == 1) {
                res = (res * i) % MOD;
            }    
            i = (i * i) % MOD;
            pow = (int) Math.floor(pow / 2.0);
        }
        
        return res;
    }
          
    public static int legoBlocks(int n, int m) {
    
        final long MOD = (long) Math.pow(10,9) + 7;
        //this is a tetranacci sequence, OEIS A000078. http://oeis.org/A000078
        //in combination with a bit of Coin Change problem
        //we should find number of combinations to build a wall of 1 unit high first
        //there is only 1 way to build wall of w == 0|1 and h == 1
        //  block/width 0   1   2   3   4   5   6
        //  1           1   1   1   1   1   1   1   is there a mononacci sequence for constant??
        //  2           1   1   2   3   5   8   13  fibonacci : 2 blocks 1-2 block 3rd onward
        //  3           1   1   2   4   7   13  24  tribonacci : 3 blocks 1-3 block 4th onward
        //  4           1   1   2   4   8   15  29  tetranacci : 4 blocks 1-4 block 5th onward
        //So for this problem with 4 kinds of blocks, we should only forcus on
        //      the tetranacci and how to implement it

        ArrayList<Long> singleRow = new ArrayList<>();
        singleRow.add(1L);
        singleRow.add(1L);
        singleRow.add(2L);
        singleRow.add(4L);
        singleRow.add(8L);

        ArrayList<Long> allRows = new ArrayList<>();

        ArrayList<Long> solid = new ArrayList<>();
        solid.add(1L);
        solid.add(1L);

        for (int i = 0; i <= m; i ++) {
            if (i > 4) {
                long sum = 0;
                for (int j = i - 1; j >= i - 4; j--) {
                    sum += singleRow.get(j);
                }
                sum = modBig(sum, MOD);
                singleRow.add(sum);
            }
            
            allRows.add(modPow(singleRow.get(i), n, MOD));
            
            if (i >= 2) {
                long allAtI = allRows.get(i);
                long solidAtI = allAtI;
                for (int j = i - 1; j >= 1; j --) {
                    long solidAtJ = solid.get(j);
                    long allAtIJ = allRows.get(i - j);
                    solidAtI = modBig(solidAtI - solidAtJ * allAtIJ, MOD);
                }
                solid.add(solidAtI);   
            }
        }
        return (int) (solid.get(m) % MOD);
    }
}