結果

問題 No.660 家を通り過ぎないランダムウォーク問題
ユーザー anta
提出日時 2018-03-02 23:10:31
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 81 ms / 2,000 ms
コード長 36,759 bytes
コンパイル時間 3,314 ms
コンパイル使用メモリ 219,088 KB
実行使用メモリ 14,332 KB
最終ジャッジ日時 2024-06-22 06:08:32
合計ジャッジ時間 4,866 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include "bits/stdc++.h"
#include <emmintrin.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
namespace uint_util {
    template<typename T> struct Utils {};
    template<> struct Utils<uint32_t> {
        static void umul_full(uint32_t a, uint32_t b, uint32_t *lo, uint32_t *hi) {
            const uint64_t c = (uint64_t)a * b;
            *lo = (uint32_t)c;
            *hi = (uint32_t)(c >> 32);
        }
        static  uint32_t umul_hi(uint32_t a, uint32_t b) {
            return (uint32_t)((uint64_t)a * b >> 32);
        }
        static uint32_t mulmod_invert(uint32_t b, uint32_t n) {
            return ((uint64_t)b << 32) / n;
        }
        static uint32_t umul_lo(uint32_t a, uint32_t b) {
            return a * b;
        }
        static uint32_t mulmod_precalculated(uint32_t a, uint32_t b, uint32_t n, uint32_t bninv) {
            const auto q = umul_hi(a, bninv);
            uint32_t r = a * b - q * n;
            if (r >= n) r -= n;
            return r;
        }
        static uint32_t invert_twoadic(uint32_t x) {
            uint32_t i = x, p;
            do {
                p = i * x;
                i *= 2 - p;
            } while (p != 1);
            return i;
        }
    };
}
namespace modnum {
    template<typename NumType> struct ModNumTypes {
        using Util = uint_util::Utils<NumType>;
        template<int Lazy> struct LazyModNum;
        //x < Lazy * P
        template<int Lazy>
        struct LazyModNum {
            NumType x;
            LazyModNum() : x() {}
            template<int L>
            explicit LazyModNum(LazyModNum<L> t) : x(t.x) { static_assert(L <= Lazy, "invalid conversion"); }
            static LazyModNum raw(NumType x) {
                LazyModNum r; r.x = x;
                return r;
            }
            template<int L>
            static LazyModNum *coerceArray(LazyModNum<L> *a) { return reinterpret_cast<LazyModNum*>(a); }
            bool operator==(LazyModNum that) const {
                static_assert(Lazy == 1, "cannot compare");
                return x == that.x;
            }
        };
        typedef LazyModNum<1> ModNum;
        class ModInfo {
        public:
            enum {
                MAX_ROOT_ORDER = 23
            };
        private:
            NumType P, P2;
            ModNum _one;
            NumType _twoadic_inverse;
            NumType _order;
            NumType _one_P_inv; //floor(W * (W rem P) / P)
            bool _support_fft;
            ModNum _roots[MAX_ROOT_ORDER + 1], _inv_roots[MAX_ROOT_ORDER + 1];
            ModNum _inv_two_powers[MAX_ROOT_ORDER + 1];
        public:
            NumType getP() const { return P; }
            NumType get_twoadic_inverse() const { return _twoadic_inverse; }
            ModNum one() const { return _one; }
            ModNum to_alt(NumType x) const {
                return ModNum::raw(Util::mulmod_precalculated(x, _one.x, P, _one_P_inv));
            }
            NumType from_alt(ModNum x) const {
                return _reduce(x.x, 0);
            }
            bool support_fft() const { return _support_fft; }
            ModNum root(int n) const {
                assert(support_fft());
                if (n > 0) {
                    assert(n <= MAX_ROOT_ORDER);
                    return _roots[n];
                } else if (n < 0) {
                    assert(n >= -MAX_ROOT_ORDER);
                    return _inv_roots[-n];
                } else {
                    return one();
                }
            }
            ModNum inv_two_power(int n) const {
                assert(support_fft());
                assert(0 <= n && n <= MAX_ROOT_ORDER);
                return _inv_two_powers[n];
            }
            ModNum add(ModNum a, ModNum b) const {
                auto c = a.x + b.x;
                if (c >= P) c -= P;
                return ModNum::raw(c);
            }
            ModNum sub(ModNum a, ModNum b) const {
                auto c = a.x + (P - b.x);
                if (c >= P) c -= P;
                return ModNum::raw(c);
            }
            LazyModNum<4> add_lazy(LazyModNum<2> a, LazyModNum<2> b) const {
                return LazyModNum<4>::raw(a.x + b.x);
            }
            LazyModNum<4> sub_lazy(LazyModNum<2> a, LazyModNum<2> b) const {
                return LazyModNum<4>::raw(a.x + (P2 - b.x));
            }
            ModNum mul(ModNum a, ModNum b) const {
                NumType lo, hi;
                Util::umul_full(a.x, b.x, &lo, &hi);
                return ModNum::raw(_reduce(lo, hi));
            }
            ModNum sqr(ModNum a) const {
                return mul(a, a);
            }
            template<int LA, int LB>
            LazyModNum<2> mul_lazy(LazyModNum<LA> a, LazyModNum<LB> b) const {
                static_assert(LA + LB <= 5, "too lazy");
                NumType lo, hi;
                Util::umul_full(a.x, b.x, &lo, &hi);
                return LazyModNum<2>::raw(_reduce_lazy(lo, hi));
            }
            ModNum pow(ModNum a, NumType k) const {
                LazyModNum<2> base{ a }, res{ one() };
                while (1) {
                    if (k & 1) res = mul_lazy(res, base);
                    if (k >>= 1) base = mul_lazy(base, base);
                    else break;
                }
                return lazy_reduce_1(res);
            }
            ModNum inverse(ModNum a) const {
                return pow(a, _order - 1);
            }
            //a < 2P, res < P
            ModNum lazy_reduce_1(LazyModNum<2> a) const {
                NumType x = a.x;
                if (x >= P) x -= P;
                return ModNum::raw(x);
            }
            //a < 4P, res < 2P
            LazyModNum<2> lazy_reduce_2(LazyModNum<4> a) const {
                NumType x = a.x;
                if (x >= P2) x -= P2;
                return LazyModNum<2>::raw(x);
            }
        private:
            NumType _reduce(NumType lo, NumType hi) const {
                const auto q = Util::umul_lo(lo, _twoadic_inverse);
                const auto h = Util::umul_hi(q, P);
                NumType t = hi + P - h;
                if (t >= P) t -= P;
                return t;
            }
            NumType _reduce_lazy(NumType lo, NumType hi) const {
                const auto q = Util::umul_lo(lo, _twoadic_inverse);
                const auto h = Util::umul_hi(q, P);
                return hi + P - h;
            }
        public:
            static ModInfo make(NumType P, NumType order = NumType(-1)) {
                ModInfo res;
                res.P = P;
                res.P2 = P * 2;
                res._one.x = ~Util::umul_lo(Util::mulmod_invert(1, P), P) + 1;
                res._order = order == NumType(-1) ? P - 1 : order;
                res._twoadic_inverse = Util::invert_twoadic(P);
                res._one_P_inv = Util::mulmod_invert(res._one.x, P);
                res._support_fft = false;
                assert(res.mul(res.one(), res.one()) == res.one());
                return res;
            }
            static ModInfo make_support_fft(NumType P, NumType order, NumType original_root, int valuation) {
                ModInfo res = make(P, order);
                _compute_fft_info(res, original_root, valuation);
                return res;
            }
        private:
            static void _compute_fft_info(ModInfo &res, NumType original_root, int valuation) {
                assert(res.P <= 1ULL << (sizeof(NumType) * 8 - 2));
                assert(valuation >= MAX_ROOT_ORDER);
                res._support_fft = true;
                ModNum max_root = res.to_alt(original_root);
                for (int i = valuation; i > MAX_ROOT_ORDER; -- i)
                    max_root = res.sqr(max_root);
                res._roots[MAX_ROOT_ORDER] = max_root;
                for (int i = MAX_ROOT_ORDER - 1; i >= 0; -- i)
                    res._roots[i] = res.sqr(res._roots[i + 1]);
                res._inv_roots[MAX_ROOT_ORDER] = res.inverse(max_root);
                for (int i = MAX_ROOT_ORDER - 1; i >= 0; -- i)
                    res._inv_roots[i] = res.sqr(res._inv_roots[i + 1]);
                res._inv_two_powers[0] = res.one();
                res._inv_two_powers[1] = res.inverse(res.add(res.one(), res.one()));
                for (int i = 1; i < MAX_ROOT_ORDER; ++ i)
                    res._inv_two_powers[i] = res.mul(res._inv_two_powers[1], res._inv_two_powers[i - 1]);
                assert(res.mul(res._roots[1], res._inv_roots[1]) == res.one());
                assert(res.root(0) == res.one());
                assert(!(res.root(1) == res.one()));
            }
        };
    };
}
namespace fft {
    using namespace modnum;
    using NumType = uint32_t;
    using ModNumType = ModNumTypes<NumType>;
    template<int Lazy>
    using LazyModNum = ModNumType::LazyModNum<Lazy>;
    using ModNum = ModNumType::ModNum;
    using ModInfo = ModNumType::ModInfo;
    using ModNumType32 = ModNumTypes<uint32_t>;
    using ModNum32 = ModNumType32::ModNum;
    using ModInfo32 = ModNumType32::ModInfo;
    inline __m128i mod_lazy_reduce_2_sse2(const __m128i &a, const __m128i &p2, const __m128i &signbit) {
        const auto mask = _mm_cmpgt_epi32(_mm_xor_si128(p2, signbit), _mm_xor_si128(a, signbit));
        const auto sub = _mm_andnot_si128(mask, p2);
        return _mm_sub_epi32(a, sub);
    }
    inline __m128i mod_reduce_lazy_sse2(const __m128i &a, const __m128i &p, const __m128i &twoadic_inverse) {
        const auto q = _mm_mul_epu32(a, twoadic_inverse);
        const auto h = _mm_shuffle_epi32(_mm_mul_epu32(q, p), _MM_SHUFFLE(3, 3, 1, 1));
        return _mm_add_epi32(a, _mm_sub_epi32(p, h));
    }
    inline __m128i mod_mul_lazy_sse2(const __m128i &a, const __m128i &b, const __m128i &p, const __m128i &twoadic_inverse) {
        const auto a02 = _mm_shuffle_epi32(a, _MM_SHUFFLE(2, 2, 0, 0));
        const auto a13 = _mm_shuffle_epi32(a, _MM_SHUFFLE(3, 3, 1, 1));
        const auto b02 = _mm_shuffle_epi32(b, _MM_SHUFFLE(2, 2, 0, 0));
        const auto b13 = _mm_shuffle_epi32(b, _MM_SHUFFLE(3, 3, 1, 1));
        const auto prod02 = _mm_mul_epu32(a02, b02);
        const auto prod13 = _mm_mul_epu32(a13, b13);
        const auto res02 = mod_reduce_lazy_sse2(prod02, p, twoadic_inverse);
        const auto res13 = mod_reduce_lazy_sse2(prod13, p, twoadic_inverse);
        const auto shuffled02 = _mm_shuffle_epi32(res02, _MM_SHUFFLE(0, 0, 3, 1));
        const auto shuffled13 = _mm_shuffle_epi32(res13, _MM_SHUFFLE(0, 0, 3, 1));
        return _mm_unpacklo_epi32(shuffled02, shuffled13);
    }
    inline __m128i mod_mul_sse2(const __m128i &a, const __m128i &b, const __m128i &p, const __m128i &twoadic_inverse) {
        __m128i t = mod_mul_lazy_sse2(a, b, p, twoadic_inverse);
        const auto mask = _mm_cmpgt_epi32(p, t);    //signed compare
        const auto sub = _mm_andnot_si128(mask, p);
        return _mm_sub_epi32(t, sub);
    }
    inline __m128i mod_add_lazy_sse2(const __m128i &a, const __m128i &b) {
        return _mm_add_epi32(a, b);
    }
    inline __m128i mod_sub_lazy_sse2(const __m128i &a, const __m128i &b, const __m128i &p2) {
        return _mm_add_epi32(a, _mm_sub_epi32(p2, b));
    }
    void ntt_dit_lazy_core_sse2(LazyModNum<2> *f_inout, int n, int sign, const ModInfo &mod) {
        LazyModNum<4> * const f = LazyModNum<4>::coerceArray(f_inout);
        int N = 1 << n;
        if (n <= 1) {
            if (n == 0)
                return;
            const auto a = f_inout[0];
            const auto b = f_inout[1];
            f_inout[0] = mod.lazy_reduce_2(mod.add_lazy(a, b));
            f_inout[1] = mod.lazy_reduce_2(mod.sub_lazy(a, b));
            return;
        }
        if (n & 1) {
            for (int i = 0; i < N; i += 2) {
                const auto a = f_inout[i + 0];
                const auto b = f_inout[i + 1];
                f[i + 0] = mod.add_lazy(a, b);
                f[i + 1] = mod.sub_lazy(a, b);
            }
        }
        if ((n & 1) == 0) {
            const auto imag = mod.root(2 * sign);
            for (int i = 0; i < N; i += 4) {
                const auto a0 = f_inout[i + 0];
                const auto a2 = f_inout[i + 1];
                const auto a1 = f_inout[i + 2];
                const auto a3 = f_inout[i + 3];
                const auto t02 = mod.lazy_reduce_2(mod.add_lazy(a0, a2));
                const auto t13 = mod.lazy_reduce_2(mod.add_lazy(a1, a3));
                f[i + 0] = mod.add_lazy(t02, t13);
                f[i + 2] = mod.sub_lazy(t02, t13);
                const auto u02 = mod.lazy_reduce_2(mod.sub_lazy(a0, a2));
                const auto u13 = mod.mul_lazy(mod.sub_lazy(a1, a3), imag);
                f[i + 1] = mod.add_lazy(u02, u13);
                f[i + 3] = mod.sub_lazy(u02, u13);
            }
        } else {
            const auto imag = mod.root(2 * sign);
            const auto omega = mod.root(3 * sign);
            for (int i = 0; i < N; i += 8) {
                const auto a0 = mod.lazy_reduce_2(f[i + 0]);
                const auto a2 = mod.lazy_reduce_2(f[i + 2]);
                const auto a1 = mod.lazy_reduce_2(f[i + 4]);
                const auto a3 = mod.lazy_reduce_2(f[i + 6]);
                const auto t02 = mod.lazy_reduce_2(mod.add_lazy(a0, a2));
                const auto t13 = mod.lazy_reduce_2(mod.add_lazy(a1, a3));
                f[i + 0] = mod.add_lazy(t02, t13);
                f[i + 4] = mod.sub_lazy(t02, t13);
                const auto u02 = mod.lazy_reduce_2(mod.sub_lazy(a0, a2));
                const auto u13 = mod.mul_lazy(mod.sub_lazy(a1, a3), imag);
                f[i + 2] = mod.add_lazy(u02, u13);
                f[i + 6] = mod.sub_lazy(u02, u13);
            }
            ModNum w = omega, w2 = imag, w3 = mod.mul(w2, w);
            for (int i = 1; i < N; i += 8) {
                const auto a0 = mod.lazy_reduce_2(f[i + 0]);
                const auto a2 = mod.mul_lazy(f[i + 2], w2);
                const auto a1 = mod.mul_lazy(f[i + 4], w);
                const auto a3 = mod.mul_lazy(f[i + 6], w3);
                const auto t02 = mod.lazy_reduce_2(mod.add_lazy(a0, a2));
                const auto t13 = mod.lazy_reduce_2(mod.add_lazy(a1, a3));
                f[i + 0] = mod.add_lazy(t02, t13);
                f[i + 4] = mod.sub_lazy(t02, t13);
                const auto u02 = mod.lazy_reduce_2(mod.sub_lazy(a0, a2));
                const auto u13 = mod.mul_lazy(mod.sub_lazy(a1, a3), imag);
                f[i + 2] = mod.add_lazy(u02, u13);
                f[i + 6] = mod.sub_lazy(u02, u13);
            }
        }
        for (int m = 4 + (n & 1); m <= n; m += 2) {
            int M = 1 << m, M_4 = M >> 2;
            const auto o = mod.root(m * sign), o2 = mod.root((m - 1) * sign), o4 = mod.root((m - 2) * sign);
            const auto p = _mm_set1_epi32(mod.getP());
            const auto p2 = _mm_set1_epi32(mod.getP() * 2);
            const auto twoadic_inverse = _mm_set1_epi32(mod.get_twoadic_inverse());
            const auto imag = _mm_set1_epi32(mod.root(2 * sign).x);
            const auto omega = _mm_set1_epi32(o4.x);
            const auto signbit = _mm_set1_epi32((int)(1U << 31));
            __m128i w = _mm_set_epi32(mod.mul(o, o2).x, o2.x, o.x, mod.one().x);
            for (int j = 0; j < M_4; j += 4) {
                const auto w2 = mod_mul_sse2(w, w, p, twoadic_inverse);
                const auto w3 = mod_mul_sse2(w2, w, p, twoadic_inverse);
                for (int i = j; i < N; i += M) {
                    const auto f0 = _mm_loadu_si128(reinterpret_cast<__m128i*>(f + i + M_4 * 0));
                    const auto f1 = _mm_loadu_si128(reinterpret_cast<__m128i*>(f + i + M_4 * 1));
                    const auto f2 = _mm_loadu_si128(reinterpret_cast<__m128i*>(f + i + M_4 * 2));
                    const auto f3 = _mm_loadu_si128(reinterpret_cast<__m128i*>(f + i + M_4 * 3));
                    const auto a0 = mod_lazy_reduce_2_sse2(f0, p2, signbit);
                    const auto a2 = mod_mul_lazy_sse2(f1, w2, p, twoadic_inverse);
                    const auto a1 = mod_mul_lazy_sse2(f2, w, p, twoadic_inverse);
                    const auto a3 = mod_mul_lazy_sse2(f3, w3, p, twoadic_inverse);
                    const auto t02 = mod_lazy_reduce_2_sse2(mod_add_lazy_sse2(a0, a2), p2, signbit);
                    const auto t13 = mod_lazy_reduce_2_sse2(mod_add_lazy_sse2(a1, a3), p2, signbit);
                    const auto r0 = mod_add_lazy_sse2(t02, t13);
                    const auto r2 = mod_sub_lazy_sse2(t02, t13, p2);
                    const auto u02 = mod_lazy_reduce_2_sse2(mod_sub_lazy_sse2(a0, a2, p2), p2, signbit);
                    const auto u13 = mod_mul_lazy_sse2(mod_sub_lazy_sse2(a1, a3, p2), imag, p, twoadic_inverse);
                    const auto r1 = mod_add_lazy_sse2(u02, u13);
                    const auto r3 = mod_sub_lazy_sse2(u02, u13, p2);
                    _mm_storeu_si128(reinterpret_cast<__m128i*>(f + i + M_4 * 0), r0);
                    _mm_storeu_si128(reinterpret_cast<__m128i*>(f + i + M_4 * 1), r1);
                    _mm_storeu_si128(reinterpret_cast<__m128i*>(f + i + M_4 * 2), r2);
                    _mm_storeu_si128(reinterpret_cast<__m128i*>(f + i + M_4 * 3), r3);
                }
                w = mod_mul_sse2(w, omega, p, twoadic_inverse);
            }
        }
        for (int i = 0; i < N; ++ i)
            f_inout[i] = mod.lazy_reduce_2(f[i]);
    }
    void ntt_dit_lazy_core(LazyModNum<2> *f_inout, int n, int sign, const ModInfo &mod) {
        ntt_dit_lazy_core_sse2(f_inout, n, sign, mod);
    }
    template<typename T>
    void bit_reverse_permute(T *f, int n) {
        int N = 1 << n, N_2 = N >> 1, r = 0;
        for (int x = 1; x < N; ++ x) {
            int h = N_2;
            while (((r ^= h) & h) == 0) h >>= 1;
            if (r > x) swap(f[x], f[r]);
        }
    }
    void ntt_dit_lazy(LazyModNum<2> *f, int n, int sign, const ModInfo &mod) {
        bit_reverse_permute(f, n);
        ntt_dit_lazy_core(f, n, sign, mod);
    }
    template<int LF, int LG>
    void componentwise_product_lazy(LazyModNum<2> *res, const LazyModNum<LF> *f, const LazyModNum<LG> *g, int N, const ModInfo &mod) {
        for (int i = 0; i < N; ++ i)
            res[i] = mod.mul_lazy(f[i], g[i]);
    }
    void normalize_and_lazy_reduce(LazyModNum<2> *f, int n, const ModInfo &mod) {
        const auto f_out = ModNum::coerceArray(f);
        int N = 1 << n;
        ModNum inv = mod.inv_two_power(n);
        assert(mod.mul(inv, mod.to_alt(N)) == mod.one());
        for (int i = 0; i < N; ++ i)
            f_out[i] = mod.lazy_reduce_1(mod.mul_lazy(f[i], inv));
    }
    void convolute(ModNum *f_in, ModNum *g_in, int n, const ModInfo &mod) {
        assert(mod.support_fft());
        const auto f = LazyModNum<2>::coerceArray(f_in);
        const auto g = LazyModNum<2>::coerceArray(g_in);
        ntt_dit_lazy(f, n, +1, mod);
        ntt_dit_lazy(g, n, +1, mod);
        componentwise_product_lazy(f, f, g, 1 << n, mod);
        ntt_dit_lazy(f, n, -1, mod);
        normalize_and_lazy_reduce(f, n, mod);
    }
    void auto_convolute(ModNum *f_in, int n, const ModInfo &mod) {
        assert(mod.support_fft());
        const auto f = LazyModNum<2>::coerceArray(f_in);
        ntt_dit_lazy(f, n, +1, mod);
        componentwise_product_lazy(f, f, f, 1 << n, mod);
        ntt_dit_lazy(f, n, -1, mod);
        normalize_and_lazy_reduce(f, n, mod);
    }
    enum { MULTIPRIME_NUM = 3 };
    static const ModInfo fft_prime_mod0 = ModInfo::make_support_fft(998244353, -1, 31, 23);
    static const ModInfo fft_prime_mod1 = ModInfo::make_support_fft(897581057, -1, 45, 23);
    static const ModInfo fft_prime_mod2 = ModInfo::make_support_fft(880803841, -1, 211, 23);
    const ModInfo * const fft_prime_mods[MULTIPRIME_NUM] = { &fft_prime_mod0, &fft_prime_mod1, &fft_prime_mod2 };
    void multiprime_compose(ModNum32 *res, const ModInfo32 &mod_res, const ModNum *f[MULTIPRIME_NUM], int N, const ModInfo * const 
        mods[MULTIPRIME_NUM]) {
        const auto f0 = f[0], f1 = f[1], f2 = f[2];
        const auto &mod0 = *mods[0], &mod1 = *mods[1], &mod2 = *mods[2];
        const auto P0 = mod0.getP(), P1 = mod1.getP(), P2 = mod2.getP();
        const auto P_res = mod_res.getP();
        const auto t1 = mod1.inverse(mod1.to_alt(P0));
        const auto t2 = mod2.inverse(mod2.to_alt((uint64_t)P0 * P1 % P2));
        const auto p01 = mod_res.to_alt((uint64_t)P0 * P1 % P_res);
        for (int i = 0; i < N; ++ i) {
            const auto a0 = mod0.from_alt(f0[i]), a1 = mod1.from_alt(f1[i]), a2 = mod2.from_alt(f2[i]);
            const auto d1 = mod1.sub(mod1.to_alt(a1), mod1.to_alt(a0));
            const auto h1 = mod1.from_alt(mod1.mul(d1, t1));
            const auto a01 = a0 + (uint64_t)P0 * h1;
            const auto d2 = mod2.sub(mod2.to_alt(a2), mod2.to_alt(a01 % P2));
            const auto h2 = mod2.from_alt(mod2.mul(d2, t2));
            res[i] = mod_res.add(mod_res.to_alt(a01 % P_res), mod_res.mul(mod_res.to_alt(h2 % P_res), p01));
        }
    }
    void multiprime_decompose(ModNum *res[MULTIPRIME_NUM], const ModNum32 *f, int N, const ModInfo32 &f_mod, const ModInfo * const 
        mods[MULTIPRIME_NUM]) {
        for (int i = 0; i < N; ++ i) {
            const auto a = f_mod.from_alt(f[i]);
            for (int k = 0; k < MULTIPRIME_NUM; ++ k)
                res[k][i] = mods[k]->to_alt(a);
        }
    }
    void multiprime_convolute(ModNum32 *res, int resN, const ModNum32 *f, int fN, const ModNum32 *g, int gN, int n, const ModInfo32 &mod) {
        int N = 1 << n;
        assert(fN <= N && gN <= N && resN <= N);
        //implicit zero-fill
        unique_ptr<ModNum[]> workspace(new ModNum[N * MULTIPRIME_NUM * 2]);
        ModNum *fs[MULTIPRIME_NUM], *gs[MULTIPRIME_NUM];
        for (int k = 0; k < MULTIPRIME_NUM; ++ k) {
            fs[k] = workspace.get() + (k * 2 + 0) * N;
            gs[k] = workspace.get() + (k * 2 + 1) * N;
        }
        multiprime_decompose(fs, f, fN, mod, fft_prime_mods);
        multiprime_decompose(gs, g, gN, mod, fft_prime_mods);
        for (int k = 0; k < MULTIPRIME_NUM; ++ k)
            convolute(fs[k], gs[k], n, *fft_prime_mods[k]);
        multiprime_compose(res, mod, const_cast<const ModNum **>(fs), resN, fft_prime_mods);
    }
    void multiprime_auto_convolute(ModNum32 *res, int resN, const ModNum32 *f, int fN, int n, const ModInfo32 &mod) {
        int N = 1 << n;
        assert(fN <= N && resN <= N);
        unique_ptr<ModNum[]> workspace(new ModNum[N * MULTIPRIME_NUM]);
        ModNum *fs[MULTIPRIME_NUM];
        for (int k = 0; k < MULTIPRIME_NUM; ++ k)
            fs[k] = workspace.get() + k * N;
        multiprime_decompose(fs, f, fN, mod, fft_prime_mods);
        for (int k = 0; k < MULTIPRIME_NUM; ++ k)
            auto_convolute(fs[k], n, *fft_prime_mods[k]);
        multiprime_compose(res, mod, const_cast<const ModNum **>(fs), resN, fft_prime_mods);
    }
}
struct ModInt {
    using NumType = uint32_t;
    using ModNumType = modnum::ModNumTypes<NumType>;
    using ModNum = ModNumType::ModNum;
    using ModInfo = ModNumType::ModInfo;
public:
    ModNum x;
    ModInt() : x() {}
    ModInt(NumType num) : x(mod.to_alt(num)) {}
    ModInt(int num) : x(mod.to_alt(num >= 0 ? num : mod.getP() + num % (int)mod.getP())) {}
    NumType get() const { return mod.from_alt(x); }
    static ModInt raw(ModNum x) { ModInt r; r.x = x; return r; }
    static ModInt one() { return raw(mod.one()); }
    ModInt operator+(ModInt that) const { return raw(mod.add(x, that.x)); }
    ModInt &operator+=(ModInt that) { return *this = *this + that; }
    ModInt operator-(ModInt that) const { return raw(mod.sub(x, that.x)); }
    ModInt &operator-=(ModInt that) { return *this = *this - that; }
    ModInt operator-() const { return raw(mod.sub(ModNum(), x)); }
    ModInt operator*(ModInt that) const { return raw(mod.mul(x, that.x)); }
    ModInt &operator*=(ModInt that) { return *this = *this * that; }
    ModInt inverse() const { return raw(mod.inverse(x)); }
    ModInt operator/(ModInt that) const { return *this * that.inverse(); }
    ModInt &operator/=(ModInt that) { return *this = *this / that.inverse(); }
    bool operator==(ModInt that) const { return x == that.x; }
    bool operator!=(ModInt that) const { return !(*this == that); }
private:
    static ModInfo mod;
public:
    static const ModInfo &get_mod_info() { return mod; }
    static NumType getMod() { return mod.getP(); }
    static void set_mod(NumType P, NumType order = -1) {
        mod = ModInfo::make(P, order);
    }
};
ModInt::ModInfo ModInt::mod;
typedef ModInt mint;
namespace mod_polynomial {
    struct Polynomial {
        typedef mint R;
        static R ZeroR() { return R(); }
        static R OneR() { return R::one(); }
        static bool IsZeroR(R r) { return r == ZeroR(); }
        struct NumberTable {
            std::vector<R> natural_numbers;
            std::vector<R> inverse_numbers;
            std::vector<R> factorials;
            std::vector<R> inverse_factorials;
            int size() const { return (int)natural_numbers.size(); }
        };
        std::vector<R> coeffs;
        Polynomial() {}
        explicit Polynomial(R c0) : coeffs(1, c0) {}
        explicit Polynomial(R c0, R c1) : coeffs(2) { coeffs[0] = c0, coeffs[1] = c1; }
        template<typename It> Polynomial(It be, It en) : coeffs(be, en) {}
        static Polynomial Zero() { return Polynomial(); }
        static Polynomial One() { return Polynomial(OneR()); }
        static Polynomial X() { return Polynomial(ZeroR(), OneR()); }
        void resize(int n) { coeffs.resize(n); }
        void clear() { coeffs.clear(); }
        R *data() { return coeffs.empty() ? NULL : &coeffs[0]; }
        const R *data() const { return coeffs.empty() ? NULL : &coeffs[0]; }
        int size() const { return static_cast<int>(coeffs.size()); }
        bool empty() const { return coeffs.empty(); }
        int degree() const { return size() - 1; }
        bool normalized() const { return coeffs.empty() || coeffs.back() != ZeroR(); }
        bool monic() const { return !coeffs.empty() && coeffs.back() == OneR(); }
        R get(int i) const { return 0 <= i && i < size() ? coeffs[i] : ZeroR(); }
        void set(int i, R x) {
            if (size() <= i)
                resize(i + 1);
            coeffs[i] = x;
        }
        void normalize() { while (!empty() && IsZeroR(coeffs.back())) coeffs.pop_back(); }
        R evaluate(R x) const {
            if (empty()) return R();
            R r = coeffs.back();
            for (int i = size() - 2; i >= 0; -- i) {
                r *= x;
                r += coeffs[i];
            }
            return r;
        }
        Polynomial &operator+=(const Polynomial &that) {
            int m = size(), n = that.size();
            if (m < n) resize(n);
            _add(data(), that.data(), n);
            return *this;
        }
        Polynomial operator+(const Polynomial &that) const {
            return Polynomial(*this) += that;
        }
        Polynomial &operator-=(const Polynomial &that) {
            int m = size(), n = that.size();
            if (m < n) resize(n);
            _subtract(data(), that.data(), n);
            return *this;
        }
        Polynomial operator-(const Polynomial &that) const {
            return Polynomial(*this) -= that;
        }
        Polynomial &operator*=(R r) {
            _multiply_1(data(), size(), r);
            return *this;
        }
        Polynomial operator*(R r) const {
            Polynomial res;
            res.resize(size());
            _multiply_1(res.data(), data(), size(), r);
            return res;
        }
        Polynomial operator*(const Polynomial &that) const {
            Polynomial r;
            multiply(r, *this, that);
            return r;
        }
        Polynomial &operator*=(const Polynomial &that) {
            multiply(*this, *this, that);
            return *this;
        }
        static void multiply(Polynomial &res, const Polynomial &p, const Polynomial &q) {
            int pn = p.size(), qn = q.size();
            if (pn < qn)
                return multiply(res, q, p);
            if (&res == &p || &res == &q) {
                Polynomial tmp;
                multiply(tmp, p, q);
                res = tmp;
                return;
            }
            if (qn == 0) {
                res.coeffs.clear();
            } else {
                res.resize(pn + qn - 1);
                _multiply_select_method(res.data(), p.data(), pn, q.data(), qn);
            }
        }
        Polynomial operator-() const {
            Polynomial res;
            res.resize(size());
            _negate(res.data(), data(), size());
            return res;
        }
        Polynomial precomputeRevInverse(int n) const {
            Polynomial res;
            res.resize(n);
            _precompute_reverse_inverse(res.data(), n, data(), size());
            return res;
        }
        static void divideRemainderPrecomputedRevInverse(Polynomial &quot, Polynomial &rem, const Polynomial &p, const Polynomial &q, const 
            Polynomial &inv) {
            assert(&quot != &p && &quot != &q && &quot != &inv);
            int pn = p.size(), qn = q.size();
            assert(inv.size() >= pn - qn + 1);
            quot.resize(std::max(0, pn - qn + 1));
            rem.resize(qn - 1);
            _divide_remainder_precomputed_inverse(quot.data(), rem.data(), p.data(), pn, q.data(), qn, inv.data());
            quot.normalize();
            rem.normalize();
        }
        Polynomial computeRemainderPrecomputedRevInverse(const Polynomial &q, const Polynomial &inv) const {
            Polynomial quot, rem;
            divideRemainderPrecomputedRevInverse(quot, rem, *this, q, inv);
            return rem;
        }
        Polynomial powerMod(long long K, const Polynomial &q) const {
            int qn = q.size();
            assert(K >= 0 && qn > 0);
            assert(q.monic());
            if (qn == 1) return Polynomial();
            if (K == 0) return One();
            Polynomial inv = q.precomputeRevInverse(std::max(size() - qn + 1, qn));
            Polynomial p = this->computeRemainderPrecomputedRevInverse(q, inv);
            int l = 0;
            while ((K >> l) > 1) ++ l;
            Polynomial res = p;
            for (-- l; l >= 0; -- l) {
                res *= res;
                res = res.computeRemainderPrecomputedRevInverse(q, inv);
                if (K >> l & 1) {
                    res *= p;
                    res = res.computeRemainderPrecomputedRevInverse(q, inv);
                }
            }
            return res;
        }
        Polynomial reverse(int n) {
            assert(size() <= n);
            Polynomial r; r.resize(n);
            for (int i = 0; i < n; ++ i)
                r.set(n - 1 - i, get(i));
            return r;
        }
        static void clearNumberTable() {
            _numberTable = NumberTable();
        }
        static const NumberTable &getNumberTable(int size) {
            extendNumberTable(size);
            return _numberTable;
        }
        static void extendNumberTable(int size) {
            int old_size = _numberTable.size();
            if (old_size >= size)
                return;
            if (old_size * 2 > size)
                size = old_size * 2;
            NumberTable &nt = _numberTable;
            nt.natural_numbers.resize(size);
            nt.inverse_numbers.resize(size);
            nt.factorials.resize(size);
            nt.inverse_factorials.resize(size);
            if (old_size == 0) {
                nt.natural_numbers[0] = ZeroR();
                nt.inverse_numbers[0] = ZeroR();
                nt.factorials[0] = OneR();
                nt.inverse_factorials[0] = OneR();
                ++ old_size;
            }
            for (int n = old_size; n < size; ++ n) {
                nt.natural_numbers[n] = nt.natural_numbers[n - 1] + OneR();
                if (IsZeroR(nt.natural_numbers[n])) {
                    std::cerr << "No inverse of zero: " << n << std::endl;
                    std::abort();
                }
                nt.factorials[n] = nt.factorials[n - 1] * nt.natural_numbers[n];
            }
            nt.inverse_factorials[size - 1] = nt.factorials[size - 1].inverse();
            for (int n = size - 2; n >= old_size; -- n)
                nt.inverse_factorials[n] = nt.inverse_factorials[n + 1] * nt.natural_numbers[n + 1];
            for (int n = old_size; n < size; ++ n)
                nt.inverse_numbers[n] = nt.inverse_factorials[n] * nt.factorials[n - 1];
        }
        Polynomial derivative() const {
            if (empty()) return *this;
            Polynomial res;
            res.resize(size() - 1);
            _derivative(res.data(), data(), size(), getNumberTable(size()).natural_numbers.data());
            return res;
        }
        Polynomial integrate() const {
            Polynomial res;
            res.resize(size() + 1);
            _integral(res.data(), data(), size(), getNumberTable(size() + 1).inverse_numbers.data());
            return res;
        }
        Polynomial inverse(int n) const {
            Polynomial res;
            res.resize(n);
            _inverse_power_series(res.data(), n, data(), size());
            return res;
        }
        Polynomial logarithm(int n) const {
            Polynomial res;
            res.resize(n);
            const NumberTable &nt = getNumberTable(std::max(size(), n));
            _log_power_series(res.data(), n, data(), size(), nt.natural_numbers.data(), nt.inverse_numbers.data());
            return res;
        }
        Polynomial exponential(int n) const {
            Polynomial res;
            res.resize(n);
            const NumberTable &nt = getNumberTable(std::max(size(), n));
            _exp_power_series(res.data(), n, data(), size(), nt.natural_numbers.data(), nt.inverse_numbers.data());
            return res;
        }
        static int MULTIPRIME_FFT_THRESHOLD;
    private:
        static NumberTable _numberTable;
        class WorkSpaceStack;
        static void _fill_zero(R *res, int n);
        static void _copy(R *res, const R *p, int n);
        static void _negate(R *res, const R *p, int n);
        static void _add(R *p, const R *q, int n);
        static void _add(R *res, const R *p, int pn, const R *q, int qn);
        static void _subtract(R *p, const R *q, int n);
        static void _subtract(R *res, const R *p, int pn, const R *q, int qn);
        static void _multiply_select_method(R *res, const R *p, int pn, const R *q, int qn);
        static void _square_select_method(R *res, const R *p, int pn);
        static void _multiply_1(R *p, const R *q, int n, R c0);
        static void _multiply_1(R *p, int n, R c0);
        static void _multiply_power_of_two(R *res, const R *p, int n, int k);
        static void _divide_power_of_two(R *res, const R *p, int n, int k);
        static void _schoolbook_multiplication(R *res, const R *p, int pn, const R *q, int qn);
        static void _multiprime_fft(R *res, const R *p, int pn, const R *q, int qn);
        static void _reverse(R *res, const R *p, int pn);
        static void _inverse_power_series(R *res, int resn, const R *p, int pn);
        static void _precompute_reverse_inverse(R *res, int resn, const R *p, int pn);
        static void _divide_precomputed_inverse(R *res, int resn, const R *revp, int pn, const R *inv);
        static void _divide_remainder_precomputed_inverse(R *quot, R *rem, const R *p, int pn, const R *q, int qn, const R *inv);
        static void _derivative(R *res, const R *p, int pn, const R *natural_numbers);
        static void _integral(R *res, const R *p, int pn, const R *inverse_numbers);
        static void _log_power_series(R *res, int resn, const R *p, int pn, const R *natural_numbers, const R *inverse_numbers);
        static void _exp_power_series(R *res, int resn, const R *p, int pn, const R *natural_numbers, const R *inverse_numbers);
    };
    int Polynomial::MULTIPRIME_FFT_THRESHOLD = 8;
    Polynomial::NumberTable Polynomial::_numberTable;
    void Polynomial::_fill_zero(R *res, int n) {
        for (int i = 0; i < n; ++ i)
            res[i] = ZeroR();
    }
    void Polynomial::_copy(R *res, const R *p, int n) {
        for (int i = 0; i < n; ++ i)
            res[i] = p[i];
    }
    void Polynomial::_negate(R *res, const R *p, int n) {
        for (int i = 0; i < n; ++ i)
            res[i] = -p[i];
    }
    void Polynomial::_add(R *res, const R *p, int pn, const R *q, int qn) {
        for (int i = 0; i < qn; ++ i)
            res[i] = p[i] + q[i];
        _copy(res + qn, p + qn, pn - qn);
    }
    void Polynomial::_subtract(R *res, const R *p, int pn, const R *q, int qn) {
        for (int i = 0; i < qn; ++ i)
            res[i] = p[i] - q[i];
        _copy(res + qn, p + qn, pn - qn);
    }
    void Polynomial::_add(R *p, const R *q, int n) {
        _add(p, p, n, q, n);
    }
    void Polynomial::_subtract(R *p, const R *q, int n) {
        _subtract(p, p, n, q, n);
    }
    void Polynomial::_multiply_1(R *res, const R *p, int n, R c0) {
        for (int i = 0; i < n; ++ i)
            res[i] = p[i] * c0;
    }
    void Polynomial::_multiply_1(R *p, int n, R c0) {
        _multiply_1(p, p, n, c0);
    }
    void Polynomial::_multiply_power_of_two(R *res, const R *p, int n, int k) {
        assert(0 < k && k < 31);
        R mul = R(1 << k);
        _multiply_1(res, p, n, mul);
    }
    void Polynomial::_divide_power_of_two(R *res, const R *p, int n, int k) {
        assert(0 < k && k < 31);
        static const R Inv2 = R(2).inverse();
        R inv = k == 1 ? Inv2 : R(1 << k).inverse();
        _multiply_1(res, p, n, inv);
    }
    void Polynomial::_multiply_select_method(R *res, const R *p, int pn, const R *q, int qn) {
        if (pn < qn) std::swap(p, q), std::swap(pn, qn);
        assert(res != p && res != q && pn >= qn && qn > 0);
        int rn = pn + qn - 1;
        if (qn == 1) {
            _multiply_1(res, p, pn, q[0]);
        } else if (qn < MULTIPRIME_FFT_THRESHOLD) {
            _schoolbook_multiplication(res, p, pn, q, qn);
        } else {
            _multiprime_fft(res, p, pn, q, qn);
        }
    }
    void Polynomial::_square_select_method(R *res, const R *p, int pn) {
        _multiply_select_method(res, p, pn, p, pn);
    }
    void Polynomial::_schoolbook_multiplication(R *res, const R *p, int pn, const R *q, int qn) {
        if (qn == 1) {
            _multiply_1(res, p, pn, q[0]);
            return;
        }
        assert(res != p && res != q && pn >= qn && qn > 0);
        _fill_zero(res, pn + qn - 1);
        for (int i = 0; i < pn; ++ i)
            for (int j = 0; j < qn; ++ j)
                res[i + j] += p[i] * q[j];
    }
    void Polynomial::_multiprime_fft(R *res, const R *p, int pn, const R *q, int qn) {
        int resn = pn + qn - 1;
        int n = 0;
        while ((1 << n) < resn) ++ n;
        if (p == q) {
            assert(pn == qn);
            fft::multiprime_auto_convolute(reinterpret_cast<R::ModNum*>(res), resn, reinterpret_cast<const R::ModNum*>(p), pn, n, mint::get_mod_info
                ());
        } else {
            fft::multiprime_convolute(reinterpret_cast<R::ModNum*>(res), resn, reinterpret_cast<const R::ModNum*>(p), pn, reinterpret_cast<const R
                ::ModNum*>(q), qn, n, mint::get_mod_info());
        }
    }
    void Polynomial::_reverse(R *res, const R *p, int pn) {
        if (res == p) {
            std::reverse(res, res + pn);
        } else {
            for (int i = 0; i < pn; ++ i)
                res[pn - 1 - i] = p[i];
        }
    }
    void Polynomial::_inverse_power_series(R *res, int resn, const R *p, int pn) {
        if (resn == 0) return;
        assert(res != p);
        assert(pn > 0);
        assert(!IsZeroR(p[0]));
        if (p[0] != OneR()) {
            unique_ptr<R[]> tmpp(new R[pn]);
            R ic0 = p[0].inverse();
            _multiply_1(tmpp.get(), p, pn, ic0);
            _inverse_power_series(res, resn, tmpp.get(), pn);
            _multiply_1(res, resn, ic0);
            return;
        }
        unique_ptr<R[]> ws(new R[resn * 4]);
        R *tmp1 = ws.get(), *tmp2 = tmp1 + resn * 2;
        _fill_zero(res, resn);
        res[0] = p[0];
        int curn = 1;
        while (curn < resn) {
            int nextn = std::min(resn, curn * 2);
            _square_select_method(tmp1, res, curn);
            _multiply_select_method(tmp2, tmp1, std::min(nextn, curn * 2 - 1), p, std::min(nextn, pn));
            _multiply_power_of_two(res, res, curn, 1);
            _subtract(res, tmp2, nextn);
            curn = nextn;
        }
    }
    void Polynomial::_precompute_reverse_inverse(R *res, int resn, const R *p, int pn) {
        unique_ptr<R[]> ws(new R[pn]);
        R *tmp = ws.get();
        _reverse(tmp, p, pn);
        _inverse_power_series(res, resn, tmp, pn);
    }
    void Polynomial::_divide_precomputed_inverse(R *res, int resn, const R *revp, int pn, const R *inv) {
        unique_ptr<R[]> ws(new R[pn + resn]);
        R *tmp = ws.get();
        _multiply_select_method(tmp, revp, pn, inv, resn);
        _reverse(res, tmp, resn);
    }
    void Polynomial::_divide_remainder_precomputed_inverse(R *quot, R *rem, const R *p, int pn, const R *q, int qn, const R *inv) {
        if (pn < qn) {
            _copy(rem, p, pn);
            _fill_zero(rem + pn, qn - 1 - pn);
            return;
        }
        assert(qn > 0);
        assert(q[qn - 1] == OneR());
        if (qn == 1) return;
        int quotn = pn - qn + 1;
        int rn = qn - 1, tn = std::min(quotn, rn), un = tn + rn;
        unique_ptr<R[]> ws(new R[pn + un + (quot != NULL ? 0 : quotn)]);
        R *revp = ws.get(), *quotmul = revp + pn;
        if (quot == NULL) quot = quotmul + un;
        _reverse(revp, p, pn);
        _divide_precomputed_inverse(quot, quotn, revp, pn, inv);
        _multiply_select_method(quotmul, q, rn, quot, tn);
        _subtract(rem, p, rn, quotmul, rn);
    }
}
vector<mint> fact, factinv;
void nCr_computeFactinv(int N) {
    N = min(N, (int)mint::getMod() - 1);
    fact.resize(N + 1); factinv.resize(N + 1);
    fact[0] = 1;
    rer(i, 1, N) fact[i] = fact[i - 1] * i;
    factinv[N] = fact[N].inverse();
    for (int i = N; i >= 1; i --) factinv[i - 1] = factinv[i] * i;
}
mint nCr(int n, int r) {
    return r > n ? 0 : fact[n] * factinv[n - r] * factinv[r];
}
mint catalan_number(int n) {
    return n == 0 ? 1 : nCr(2 * n, n) - nCr(2 * n, n - 1);
}
int main() {
    mint::set_mod((int)1e9 + 7);
    int N;
    while (~scanf("%d", &N)) {
        nCr_computeFactinv(N * 2);
        mint ans;
        const int K = N / 2 + 1;
        using Polynomial = mod_polynomial::Polynomial;
        Polynomial poly, catalan;
        rep(k, K)
            poly.set(k, nCr(N + k * 2, k));
        catalan.set(0, 1);
        rep(k, K)
            catalan.set(k + 1, -catalan_number(k) * 2);
        const auto prod = poly * catalan;
        rep(k, K)
            ans += prod.get(k);
        printf("%d\n", ans.get());
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0