//EGOI 2022 Lego Wall
//https://qoj.ac/contest/2259/problem/5179
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
const ll MAXN = 5e5+5;
const ll MOD = 1e9+7;
vll f(MAXN,1), fi(MAXN);
ll binpow(ll a,ll b){
ll res=1;
while(b){
if(b&1) res=(res*a)%MOD;
a=(a*a)%MOD; b/=2;
}
return res;
}
void setup(){
for(int i=1; i<MAXN; i++) f[i]=(f[i-1]*i)%MOD;
fi[MAXN-1]=binpow(f[MAXN-1],MOD-2);
for(int i=MAXN-2; i>=0; i--) fi[i]=(fi[i+1]*(i+1))%MOD;
}
ll binom(ll a,ll b){return ((f[a]*fi[b])%MOD*fi[a-b])%MOD;}
int main(){
ll n, m, ans=0; setup();
cin >> n >> m;
if(m<n){
vll dp(m+1,0); dp[m]=1;
for(int i=2; i<=n; i++){
vll ndp(m+1,0);
for(int x=0; x<m; x++) for(int y=m-x; y<=m; y++){
ndp[x]=(ndp[x]+dp[y]*binom(y,m-x))%MOD;
}
swap(dp,ndp);
}
for(int i=0; i<=m; i++) ans=(ans+dp[i])%MOD;
}else{
vll fib(n+1,0), dp(n+1,1); vector<vll> tot(n+1,vll(m+1,1)); fib[0]=1; fib[1]=2;
for(int i=2; i<=n; i++) fib[i]=(fib[i-1]+fib[i-2])%MOD;
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) tot[i][j]=(tot[i][j-1]*fib[i-1])%MOD;
for(int i=2; i<=n; i++){
dp[i]=tot[i][m];
for(int j=1; j<i; j++) dp[i]=(dp[i]-(dp[j]*tot[i-j][m])%MOD+MOD)%MOD;
}
ans=dp[n];
}
cout << ans << "\n";
}
