#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MOD = 1000000007;
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;
}
vector<long long> berlekamp_massey(const vector<long long>& s) {
vector<long long> C = {1}, B = {1};
int L = 0;
long long m = 1;
for (int i = 0; i < s.size(); i++) {
long long d = 0;
for (int j = 0; j <= L; j++) {
d = (d + C[j] * s[i - j]) % MOD;
}
if (d == 0) {
B.insert(B.begin(), 0);
continue;
}
vector<long long> temp = C;
long long c = (d * power(m, MOD - 2)) % MOD;
while (C.size() <= B.size() + 1) C.push_back(0);
for (int j = 0; j < B.size(); j++) {
C[j + 1] = (C[j + 1] - c * B[j]) % MOD;
if (C[j + 1] < 0) C[j + 1] += MOD;
}
if (2 * L <= i) {
L = i + 1 - L;
B = temp;
m = d;
} else {
B.insert(B.begin(), 0);
}
}
return C;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int w, h;
if (!(cin >> w >> h)) return 0;
vector<long long> row(w + 1, 0);
row[0] = 1;
if (w >= 1) row[1] = 1;
for (int i = 2; i <= w; i++) {
row[i] = (row[i - 1] + row[i - 2]) % MOD;
}
vector<long long> total(w + 1, 0);
for (int i = 0; i <= w; i++) {
total[i] = power(row[i], h);
}
vector<long long> dp(w + 1, 0);
if (w >= 1) dp[1] = total[1];
if (w <= 1500) {
for (int i = 2; i <= w; i++) {
long long bad = 0;
for (int j = 1; j < i; j++) {
bad = (bad + dp[j] * total[i - j]) % MOD;
}
dp[i] = (total[i] - bad + MOD) % MOD;
}
} else {
int bm_limit = min((int)total.size() - 1, 2 * h + 2);
vector<long long> bm_input(total.begin(), total.begin() + bm_limit + 1);
vector<long long> C = berlekamp_massey(bm_input);
vector<long long> P(h + 2, 0);
for (int k = 0; k <= min(h + 1, (int)C.size() - 1); k++) {
for (int j = 0; j <= k; j++) {
if (j < C.size()) {
P[k] = (P[k] + total[k - j] * C[j]) % MOD;
}
}
}
int dp_limit = min(w, h + 1);
for (int i = 2; i <= dp_limit; i++) {
long long bad = 0;
for (int j = 1; j < i; j++) {
bad = (bad + dp[j] * total[i - j]) % MOD;
}
dp[i] = (total[i] - bad + MOD) % MOD;
}
for (int i = dp_limit + 1; i <= w; i++) {
long long val = 0;
for (int j = 1; j <= h + 1; j++) {
if (i - j < 1) break;
val = (val + P[j] * dp[i - j]) % MOD;
}
dp[i] = (-val % MOD + MOD) % MOD;
}
}
cout << dp[w] << "\n";
return 0;
}
