import java.util.ArrayList;

public class Euler654 {

    static final long kMod = 1000000007L;

    static long modAdd(long a, long b) {
        a += b;
        return (a >= kMod) ? (a - kMod) : a;
    }

    static long modSub(long a, long b) {
        return (a >= b) ? (a - b) : (a + kMod - b);
    }

    static long modMul(long a, long b) {
        return (a * b) % kMod;
    }

    static long modPow(long base, long exp) {
        long result = 1;
        base %= kMod;
        while (exp > 0) {
            if ((exp & 1) != 0)
                result = modMul(result, base);
            base = modMul(base, base);
            exp >>= 1;
        }
        return result;
    }

    static ArrayList<Long> buildSequence(int n, int terms) {
        int states = n - 1;
        long[] vec = new long[states];
        long[] prefix = new long[states];
        long[] nextVec = new long[states];
        for (int i = 0; i < states; i++)
            vec[i] = 1;

        ArrayList<Long> seq = new ArrayList<>(terms);

        for (int step = 1; step <= terms; ++step) {
            long total = 0;
            for (int i = 0; i < states; ++i) {
                total += vec[i];
            }
            total %= kMod;
            seq.add(total);

            long run = 0;
            for (int i = 0; i < states; ++i) {
                run += vec[i];
                if (run >= kMod)
                    run -= kMod;
                prefix[i] = run;
            }

            for (int j = 0; j < states; ++j) {
                nextVec[j] = prefix[states - 1 - j];
            }
            long[] tmp = vec;
            vec = nextVec;
            nextVec = tmp;
        }

        return seq;
    }

    static ArrayList<Long> berlekampMassey(ArrayList<Long> s) {
        ArrayList<Long> C = new ArrayList<>();
        ArrayList<Long> B = new ArrayList<>();
        C.add(1L);
        B.add(1L);
        int L = 0;
        int m = 1;
        long b = 1;

        for (int n = 0; n < s.size(); ++n) {
            long d = s.get(n);
            for (int i = 1; i <= L; ++i) {
                d = (d + modMul(C.get(i), s.get(n - i))) % kMod;
            }

            if (d == 0) {
                ++m;
                continue;
            }

            ArrayList<Long> T = new ArrayList<>(C);
            long coef = modMul(d, modPow(b, kMod - 2));

            while (C.size() < B.size() + m) {
                C.add(0L);
            }

            for (int i = 0; i < B.size(); ++i) {
                int idx = i + m;
                C.set(idx, modSub(C.get(idx), modMul(coef, B.get(i))));
            }

            if (2 * L <= n) {
                L = n + 1 - L;
                B = T;
                b = d;
                m = 1;
            } else {
                ++m;
            }
        }

        ArrayList<Long> rec = new ArrayList<>(L);
        for (int i = 1; i <= L; ++i) {
            rec.add(modSub(0, C.get(i)));
        }
        return rec;
    }

    static long[] combinePoly(long[] a, long[] b, long[] rec) {
        int k = rec.length;
        long[] tmp = new long[2 * k - 1];

        for (int i = 0; i < a.length; ++i) {
            if (a[i] == 0)
                continue;
            for (int j = 0; j < b.length; ++j) {
                if (b[j] == 0)
                    continue;
                tmp[i + j] = (tmp[i + j] + modMul(a[i], b[j])) % kMod;
            }
        }

        for (int i = 2 * k - 2; i >= k; --i) {
            long x = tmp[i];
            if (x == 0)
                continue;
            for (int t = 1; t <= k; ++t) {
                int idx = i - t;
                tmp[idx] = (tmp[idx] + modMul(x, rec[t - 1])) % kMod;
            }
        }

        long[] ret = new long[k];
        System.arraycopy(tmp, 0, ret, 0, k);
        return ret;
    }

    static long linearRecurrenceNth(ArrayList<Long> initList, ArrayList<Long> recList, long nOneBased) {
        int k = recList.size();
        if (nOneBased <= k)
            return initList.get((int) (nOneBased - 1));

        long[] rec = new long[k];
        long[] init = new long[k];
        for (int i = 0; i < k; i++) {
            rec[i] = recList.get(i);
            init[i] = initList.get(i);
        }

        long exp = nOneBased - 1;
        long[] result = new long[k];
        result[0] = 1;

        long[] base = new long[k];
        if (k == 1) {
            base[0] = rec[0];
        } else {
            base[1] = 1;
        }

        while (exp > 0) {
            if ((exp & 1) != 0) {
                result = combinePoly(result, base, rec);
            }
            exp >>= 1;
            if (exp > 0) {
                base = combinePoly(base, base, rec);
            }
        }

        long ans = 0;
        for (int i = 0; i < k; ++i) {
            ans = (ans + modMul(result[i], init[i])) % kMod;
        }
        return ans;
    }

    static long solveCase(int n, long m) {
        int needTerms = 2 * (n - 1) + 8;
        ArrayList<Long> seq = buildSequence(n, needTerms);
        if (m <= seq.size())
            return seq.get((int) (m - 1));

        ArrayList<Long> rec = berlekampMassey(seq);
        int k = rec.size();
        ArrayList<Long> init = new ArrayList<>(seq.subList(0, k));
        return linearRecurrenceNth(init, rec, m);
    }

    public static String solve() {
        long ans = solveCase(5000, 1000000000000L);
        return Long.toString(ans);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}