#include <iostream>
#include <vector>
using namespace std;
/**
* Problem: Lego Wall
* Goal: Find the number of solid walls of height H and width W.
* A wall is "solid" if no vertical line cuts through it completely.
*/
long long H, W;
const int MOD = 1e9 + 7;
// Helper function for modular exponentiation: (base^exp) % MOD
long long power(long long base, long long exp) {
long long res = 1;
base %= MOD;
while (exp > 0) {
if (exp % 2 == 1) res = (res * base) % MOD;
base = (base * base) % MOD;
exp /= 2;
}
return res;
}
/**
* Approach 1: Used when Width is small (W < 5000).
* Uses DP + Inclusion-Exclusion.
*/
void solve_small_width() {
// total_ways_row[i] = number of ways to fill a 1 x i row with 1x1 and 1x2 bricks
// This is essentially the Fibonacci sequence.
vector<long long> total_ways_row(W + 1);
total_ways_row[0] = 1;
total_ways_row[1] = 1;
for (int i = 2; i <= W; i++) {
total_ways_row[i] = (total_ways_row[i - 1] + total_ways_row[i - 2]) % MOD;
}
// wall_combinations[i] = total ways to build a wall of height H and width i
// Each of the H rows is independent, so it's (ways_per_row)^H
vector<long long> wall_combinations(W + 1);
for (int i = 1; i <= W; i++) {
wall_combinations[i] = power(total_ways_row[i], H);
}
// solid_walls[i] = number of walls of width i that are "solid"
// Calculation: Total combinations - Non-solid combinations
vector<long long> solid_walls(W + 1);
for (int i = 1; i <= W; i++) {
solid_walls[i] = wall_combinations[i];
for (int j = 1; j < i; j++) {
// Subtract walls where the FIRST vertical seam occurs at position j
long long non_solid = (solid_walls[j] * wall_combinations[i - j]) % MOD;
solid_walls[i] = (solid_walls[i] - non_solid + MOD) % MOD;
}
}
cout << solid_walls[W] << endl;
}
/**
* Approach 2: Used when Height is small (H < 105).
* Uses DP based on "bridging" bricks between columns.
*/
void solve_small_height() {
// Precompute Binomial Coefficients (nCr)
vector<vector<long long>> nCr(H + 1, vector<long long>(H + 1, 0));
for (int i = 0; i <= H; i++) {
nCr[i][0] = 1;
for (int j = 1; j <= i; j++) {
nCr[i][j] = (nCr[i - 1][j - 1] + nCr[i - 1][j]) % MOD;
}
}
// dp[col][bridges] = ways to have 'bridges' number of 2x1 bricks
// crossing from current column to the next column.
vector<vector<long long>> dp(W, vector<long long>(H + 1, 0));
// Base case: First column gap (between col 1 and col 2)
for (int j = 1; j <= H; j++) {
dp[1][j] = nCr[H][j];
}
// Transition through each column
for (int i = 2; i < W; i++) {
for (int j = 1; j <= H; j++) { // bridges to the next column
for (int k = 1; k <= H - j; k++) { // bridges from the previous column
// We can only place a bridge in a row that doesn't already have one
long long ways = (dp[i - 1][k] * nCr[H - k][j]) % MOD;
dp[i][j] = (dp[i][j] + ways) % MOD;
}
}
}
// Sum all ways to reach the final column gap with at least one bridge
long long total_solid_walls = 0;
for (int j = 1; j <= H; j++) {
total_solid_walls = (total_solid_walls + dp[W - 1][j]) % MOD;
}
cout << total_solid_walls << endl;
}
int main() {
// Fast I/O
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (!(cin >> W >> H)) return 0;
// The original code switches logic based on constraints
if (W < 5000) {
solve_small_width();
} else {
solve_small_height();
}
return 0;
}
