public class Euler631 {
    static final long MOD = 1000000007L;

    public static String solve() {
        int m = 40;
        long n = 1000000000000000000L;
        int dim_inv = m + 1;
        int dim_last132 = m + 3;
        int dim_last21 = m + 3;
        int plane = dim_last132 * dim_last21;
        int total_states = dim_inv * plane;

        long[] cur = new long[total_states];
        cur[m * plane + 0] = 1;

        long total = 1;
        int max_len = m + 2;
        int limit = (n < max_len) ? (int) n : max_len;

        for (int length = 1; length <= limit; ++length) {
            long[] nxt = new long[total_states];
            for (int inv = 0; inv <= m; ++inv) {
                int upper = (inv + 1 < length) ? (inv + 1) : length;
                if (upper <= 0)
                    continue;
                for (int last132p1 = 0; last132p1 <= length; ++last132p1) {
                    int start = last132p1;
                    if (start >= upper)
                        continue;
                    for (int last21 = 0; last21 < length; ++last21) {
                        long cnt = cur[inv * plane + last132p1 * dim_last21 + last21];
                        if (cnt == 0)
                            continue;
                        for (int i = start; i < upper; ++i) {
                            total = (total + cnt) % MOD;
                            if (i < last21) {
                                int idx_val = (inv - i) * plane + (i + 1) * dim_last21 + (last21 + 1);
                                nxt[idx_val] = (nxt[idx_val] + cnt) % MOD;
                            } else {
                                int idx_val = (inv - i) * plane + last132p1 * dim_last21 + i;
                                nxt[idx_val] = (nxt[idx_val] + cnt) % MOD;
                            }
                        }
                    }
                }
            }
            cur = nxt;
        }

        if (n <= max_len)
            return Long.toString(total);

        long g = 0;
        for (long v : cur) {
            g = (g + v) % MOD;
        }

        long extra = ((n - max_len) % MOD) * g % MOD;
        return Long.toString((total + extra) % MOD);
    }

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