For this Question: Newton is currently standing at the origin (0, 0), at time t = 0. Each second, he will move exactly 1 unit up, down, left or right from his current position, where each direction has equal probability. Define f(x, y) as follows:

f(x, y) = 0, if the point (x, y) has been visited less than K times upto and including time t = N.

f(x, y) = t<sub>P</sub>, if the point (x, y) has been visited K or more times upto and including time t = N, and t<sub>P</sub> is the time it was visited for the P<sup>th</sup> time (P &le; K).

Let S be the sum of f(x, y) over all lattice points of the plane. You will be given Q queries to solve. In each query, you are given the integers N and P,  and you have to print the expected value of S modulo 998244353. Note that the integer K is constant for all queries.

Formally, it can be shown that the answer to each query can be expressed as an irreducible fraction <sup>p</sup>&frasl;<sub>q</sub>, where p and q are integers and gcd(q, 998244353) = 1. You have to output the integer equal to pq<sup>-1</sup> mod 998244353 for each query.

Note that the time of first visit of origin is considered to be 0.The first line of the input contains two space separated integers K (1 &le; K &le; 10<sup>5</sup>) and Q (1 &le; Q &le; 10<sup>5</sup>).

Then Q lines follow, each line containing two integers N and P for each query (1 &le; P &le; K &le; N &le; 10<sup>5</sup>).Print Q lines — each line containing a single integer with the i<sup>th</sup> line denoting the expected value of S modulo 998244353 for the i<sup>th</sup> query.Sample input 1:
1 1
2 1

Sample output 1:
499122179

Explanation 1:
The value comes out to be 5/2.

Sample input 2:
2 2
3 2
3 1

Sample Output 2:
748683266
748683265, I have written this Solution Code: // define asc
//#define dbg_local

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template <typename t>
using ordered_set = tree<t, null_type, less<t>, rb_tree_tag, tree_order_statistics_node_update>;

// #pragma gcc optimize("ofast")
// #pragma gcc target("avx,avx2,fma")



#define all(x) (x).begin(), (x).end()

#define pb push_back
#define endl '\n'
#define fi first
#define se second

// const int mod = 1e9 + 7;
const int mod=998'244'353;


const long long INF = 2e18 + 10;
// const int INF=1e9+10;

#define readv(x, n)   \
    vector<int> x(n); \
    for (auto &i : x) \
        cin >> i;



template <typename t>
    using v = vector<t>;

template <typename t>
    using vv = vector<vector<t>>;

template <typename t>
    using vvv = vector<vector<vector<t>>>;

typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<vector<vector<vector<int>>>> vvvvi;
typedef vector<vector<double>> vvd;

typedef pair<int, int> pii;



int multiply(int a, int b, int in_mod) { return (int)(1ll * a * b % in_mod); }
int mult_identity(int a) { return 1; }



const double pi = acosl(-1);



auto power(auto a, auto b, const int in_mod)
{

    auto prod = mult_identity(a);
    auto mult = a % in_mod;
    while (b != 0)
    {
        if (b % 2)
        {
            prod = multiply(prod, mult, in_mod);
        }
        if(b/2)
            mult = multiply(mult, mult, in_mod);
        b /= 2;
    }
    return prod;
}
auto mod_inv(auto q, const int in_mod)
{
    return power(q, in_mod - 2, in_mod);
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define stp cout << fixed << setprecision(20);


namespace algebra {

    using ll = long long;
    using uint = unsigned int;
    using ull = unsigned long long;
    using ld = long double;
template<typename T> using max_heap = std::priority_queue<T>;
template<typename T> using min_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;
    struct modinfo
    {
        const uint mod, root, max2p;
    };
template<const modinfo& info>
    class modint
    {
    public:
    static constexpr const uint& mod = 998244353;
    static constexpr const uint& root = 3;
    static constexpr const uint& max2p = 23;
        constexpr modint() : m_val{0} {}
        constexpr modint(const ll v) : m_val{normll(v)} {}
        constexpr modint(const modint& m) = default;
        constexpr void set_raw(const uint v) { m_val = v; }
        constexpr modint& operator=(const modint& m) { return m_val = m(), (*this); }
        constexpr modint& operator=(const ll v) { return m_val = normll(v), (*this); }
        constexpr modint operator+() const { return *this; }
        constexpr modint operator-() const { return modint{0} - (*this); }
        constexpr modint& operator+=(const modint& m) { return m_val = norm(m_val + m()), *this; }
        constexpr modint& operator-=(const modint& m) { return m_val = norm(m_val + mod - m()), *this; }
        constexpr modint& operator*=(const modint& m) { return m_val = normll((ll)m_val * (ll)m() % (ll)mod), *this; }
        constexpr modint& operator/=(const modint& m) { return *this *= m.inv(); }
        constexpr modint& operator+=(const ll val) { return *this += modint{val}; }
        constexpr modint& operator-=(const ll val) { return *this -= modint{val}; }
        constexpr modint& operator*=(const ll val) { return *this *= modint{val}; }
        constexpr modint& operator/=(const ll val) { return *this /= modint{val}; }
        constexpr modint operator+(const modint& m) const { return modint{*this} += m; }
        constexpr modint operator-(const modint& m) const { return modint{*this} -= m; }
        constexpr modint operator*(const modint& m) const { return modint{*this} *= m; }
        constexpr modint operator/(const modint& m) const { return modint{*this} /= m; }
        constexpr modint operator+(const ll v) const { return *this + modint{v}; }
        constexpr modint operator-(const ll v) const { return *this - modint{v}; }
        constexpr modint operator*(const ll v) const { return *this * modint{v}; }
        constexpr modint operator/(const ll v) const { return *this / modint{v}; }
        constexpr bool operator==(const modint& m) const { return m_val == m(); }
        constexpr bool operator!=(const modint& m) const { return not(*this == m); }
        constexpr friend modint operator+(const ll v, const modint& m) { return modint{v} + m; }
        constexpr friend modint operator-(const ll v, const modint& m) { return modint{v} - m; }
        constexpr friend modint operator*(const ll v, const modint& m) { return modint{v} * m; }
        constexpr friend modint operator/(const ll v, const modint& m) { return modint{v} / m; }
        friend std::istream& operator>>(std::istream& is, modint& m)
        {
            ll v;
            return is >> v, m = v, is;
        }
        friend std::ostream& operator<<(std::ostream& os, const modint& m) { return os << m(); }
        constexpr uint operator()() const { return m_val; }
        constexpr modint pow(ull n) const
        {
            modint ans = 1;
            for (modint x = *this; n > 0; n >>= 1, x *= x) {
                if (n & 1ULL) { ans *= x; }
            }
            return ans;
        }
        constexpr modint inv() const { return pow(mod - 2); }
        modint sinv() const { return sinv(m_val); }
        static modint fact(const uint n)
        {
            static std::vector<modint> fs{1, 1};
            for (uint i = (uint)fs.size(); i <= n; i++) { fs.push_back(fs.back() * i); }
                return fs[n];
        }
        static modint ifact(const uint n)
        {
            static std::vector<modint> ifs{1, 1};
            for (uint i = (uint)ifs.size(); i <= n; i++) { ifs.push_back(ifs.back() * sinv(i)); }
                return ifs[n];
        }
        static modint perm(const int n, const int k) { return k > n or k < 0 ? modint{0} : fact(n) * ifact(n - k); }
        static modint comb(const int n, const int k) { return k > n or k < 0 ? modint{0} : fact(n) * ifact(n - k) * ifact(k); }
    private:
        static constexpr uint norm(const uint x) { return x < mod ? x : x - mod; }
        static constexpr uint normll(const ll x) { return norm(uint(x % (ll)mod + (ll)mod)); }
        static modint sinv(const uint n)
        {
            static std::vector<modint> is{1, 1};
            for (uint i = (uint)is.size(); i <= n; i++) { is.push_back(-is[mod % i] * (mod / i)); }
                return is[n];
        }
        uint m_val;
    };
    constexpr modinfo modinfo_1000000007 = {1000000007, 5, 1};
    constexpr modinfo modinfo_998244353 = {998244353, 3, 23};
    using modint_1000000007 = modint<modinfo_1000000007>;
    using modint_998244353 = modint<modinfo_998244353>;
    constexpr int popcount(const ull v) { return v ? __builtin_popcountll(v) : 0; }
    constexpr int log2p1(const ull v) { return v ? 64 - __builtin_clzll(v) : 0; }
    constexpr int lsbp1(const ull v) { return __builtin_ffsll(v); }
    constexpr int clog(const ull v) { return v ? log2p1(v - 1) : 0; }
    constexpr ull ceil2(const ull v) { return 1ULL << clog(v); }
    constexpr ull floor2(const ull v) { return v ? (1ULL << (log2p1(v) - 1)) : 0ULL; }
    constexpr bool btest(const ull mask, const int ind) { return (mask >> ind) & 1ULL; }
    class range
    {
    private:
        struct itr
        {
            itr(const int start = 0, const int step = 1) : m_cnt{start}, m_step{step} {}
            bool operator!=(const itr& it) const { return m_cnt != it.m_cnt; }
            int& operator*() { return m_cnt; }
            itr& operator++() { return m_cnt += m_step, *this; }
            int m_cnt, m_step;
        };
        int m_start, m_end, m_step;
    public:
        range(const int start, const int end, const int step = 1) : m_start{start}, m_end{end}, m_step{step}
        {
            assert(m_step != 0);
            if (m_step > 0) { m_end = m_start + std::max(m_step - 1, m_end - m_start + m_step - 1) / m_step * m_step; }
            if (m_step < 0) { m_end = m_start - std::max(-m_step - 1, m_start - m_end - m_step - 1) / (-m_step) * (-m_step); }
        }
        itr begin() const { return itr{m_start, m_step}; }
        itr end() const { return itr{m_end, m_step}; }
    };
    range rep(const int end, const int step = 1) { return range(0, end, step); }
    range per(const int rend, const int step = -1) { return range(rend - 1, -1, step); }
template<typename mint>
    class ntt
    {
    private:
        static constexpr const uint& mod = mint::mod;
        static constexpr const uint& root = mint::root;
        static constexpr const uint& max2p = mint::max2p;
    public:
        ntt() = delete;
        static void trans(std::vector<mint>& as, const int lg, const bool rev)
        {
            const int N = as.size();
            static std::vector<mint> rs;
            static std::vector<mint> irs;
            if (rs.empty()) {
                const mint r = mint(root), ir = r.inv();
                rs.resize(max2p + 1), irs.resize(max2p + 1);
                rs.back() = -r.pow((mod - 1) >> max2p), irs.back() = -ir.pow((mod - 1) >> max2p);
                for (uint i = max2p; i >= 1; i--) { rs[i - 1] = -(rs[i] * rs[i]), irs[i - 1] = -(irs[i] * irs[i]); }
            }
        const auto rang = (rev ? range(0, lg, 1) : range(lg - 1, -1, -1));
        for (const int d : rang) {
            const int width = 1 << d;
            mint e = 1;
            for (int i = 0, j = 1; i < N; i += width * 2, j++) {
                for (int l = i, r = i + width; l < i + width; l++, r++) {
                    const mint x = as[l], y = (rev ? as[r] : as[r] * e);
                    as[l] = x + y, as[r] = (rev ? (x - y) * e : x - y);
                }
                e *= (rev ? irs : rs)[lsbp1(j) + 1];
            }
        }
    }
    static std::vector<mint> convolute(std::vector<mint> as, std::vector<mint> bs)
    {
        const int need = as.size() + bs.size() - 1, lg = clog(need), size = 1UL << lg;
        as.resize(size), bs.resize(size);
        trans(as, lg, false), trans(bs, lg, false);
        for (int i = 0; i < size; i++) { as[i] *= bs[i]; }
            trans(as, lg, true);
        const auto isize = mint{size}.inv();
        for (int i = 0; i < need; i++) { as[i] *= isize; }
            return std::vector<mint>(as.begin(), as.begin() + need);
    }
};



template<typename mint>
class fps
{
private:

    static constexpr const uint& mod = mint::mod;
    static constexpr const uint& root = mint::root;
    static constexpr const uint& max2p = mint::max2p;
    // static constexpr modinfo info1 = {469762049, 3, 26};
    // static constexpr modinfo info2 = {167772161, 3, 25};
    // static constexpr modinfo info3 = {754974721, 11, 24};
    // using mint1 = modint<info1>;
    // using mint2 = modint<info2>;
    // using mint3 = modint<info3>;
    // static constexpr mint2 ip1 = mint2{mint1::mod}.inv();
    // static constexpr mint3 ip2 = mint3{mint2::mod}.inv();
    // static constexpr mint3 ip1p2 = mint3{mint1::mod}.inv() * mint3{mint2::mod}.inv();
    // static constexpr mint p1 = mint{mint1::mod};
    // static constexpr mint p1p2 = mint{mint1::mod} * mint{mint2::mod};
    template<typename submint>
    static std::vector<submint> conv(const std::vector<mint>& as, const std::vector<mint>& bs)
    {
        std::vector<submint> As(as.size()), Bs(bs.size());
        for (int i = 0; i < (int)as.size(); i++) { As[i] = as[i](); }
            for (int i = 0; i < (int)bs.size(); i++) { Bs[i] = bs[i](); }
                return ntt<submint>::convolute(As, Bs);
        }

    public:
        std::vector<mint> convolute(const std::vector<mint>& as, const std::vector<mint>& bs)
        {
            const int N = as.size() + bs.size() - 1;
            if (N <= (1 << max2p)) {
                return ntt<mint>::convolute(as, bs);
            } else {
                
            }
        }
    };

    const int inf = 1e9;
    const int magic = 500; // threshold for sizes to run the naive algo

    namespace fft {
        const int maxn = 1 << 19;

        typedef double ftype;
        typedef complex<ftype> point;

        vector<point> w;
        const ftype pi = acos(-1);
        bool initiated = 0;
        void init() {
            if(!initiated) {
                w.resize(maxn);
                for(int i = 1; i < maxn; i *= 2) {
                    for(int j = 0; j < i; j++) {
                        w[i + j] = polar(ftype(1),2* pi * j / i);
                    }
                }
                initiated = 1;
            }
        }
        template<typename T>
        void fft(T *in, point *out, int n) {

            for (int i = 1, j = 0; i < n; i++) {
                int bit = n >> 1;
                for (; j & bit; bit >>= 1)
                    j ^= bit;
                j ^= bit;

                if (i < j)
                    swap(in[i], in[j]);
            }

            for (int len = 2; len <= n; len <<= 1) {
                for (int i = 0; i < n; i += len) {
                    for (int j = 0; j < len / 2; j++) {
                        point u = in[i+j], v = in[i+j+len/2] * w[j  + len];
                        in[i+j] = u + v;
                        in[i+j+len/2] = u - v;
                    }
                }
            }

            for(int i= 0;i<n;i++)
                out[i] = in[i];

        }

        template<typename T>
        void mul_slow(vector<T> &a, const vector<T> &b) {
            vector<T> res(a.size() + b.size() - 1);
            for(size_t i = 0; i < a.size(); i++) {
                for(size_t j = 0; j < b.size(); j++) {
                    res[i + j] += a[i] * b[j];
                }
            }
            a = res;
        }


        template<typename T>
        void mul(vector<T> &a, const vector<T> &b) {
            if(a.size() == 0 && b.size() == 0)
            {
                a = {};
                return;
            }
            if(min(a.size(), b.size()) < magic) {
                mul_slow(a, b);
                return;
            }
            using mint = modint_998244353;
            int N = a.size();
            int M = b.size();
            std::vector<mint> as(N), bs(M);


            for(int i = 0;i<N;i++)
                as[i].set_raw(a[i]);

            for(int i = 0;i<M;i++)
                bs[i].set_raw(b[i]);
                fps<mint> aaaa;
                    const auto cs = aaaa.convolute(as, bs);

                a.resize(cs.size());

                for (int i = 0; i < (int)cs.size(); i++) { a[i] = cs[i](); }


            }
    }
    template<typename T>
    T bpow(T x, size_t n) {
        return n ? n % 2 ? x * bpow(x, n - 1) : bpow(x * x, n / 2) : T(1);
    }
    template<typename T>
    T bpow(T x, size_t n, T m) {
        return n ? n % 2 ? x * bpow(x, n - 1, m) % m : bpow(x * x % m, n / 2, m) : T(1);
    }
    template<typename T>
    T gcd(const T &a, const T &b) {
        return b == T(0) ? a : gcd(b, a % b);
    }
    template<typename T>
    T nCr(T n, int r) { // runs in O(r)
        T res(1);
        for(int i = 0; i < r; i++) {
            res *= (n - T(i));
            res /= (i + 1);
        }
        return res;
    }

    template<int m>
    struct modular {
        int64_t r;
        modular() : r(0) {}
        modular(int64_t rr) : r(rr) {if(abs(r) >= m) r %= m; if(r < 0) r += m;}
        modular inv() const {return bpow(*this, m - 2);}
        modular operator * (const modular &t) const {return (r * t.r) % m;}
        modular operator / (const modular &t) const {return *this * t.inv();}
        modular operator += (const modular &t) {r += t.r; if(r >= m) r -= m; return *this;}
        modular operator -= (const modular &t) {r -= t.r; if(r < 0) r += m; return *this;}
        modular operator + (const modular &t) const {return modular(*this) += t;}
        modular operator - (const modular &t) const {return modular(*this) -= t;}
        modular operator *= (const modular &t) {return *this = *this * t;}
        modular operator /= (const modular &t) {return *this = *this / t;}

        bool operator == (const modular &t) const {return r == t.r;}
        bool operator != (const modular &t) const {return r != t.r;}

        operator int64_t() const {return r;}
    };
    template<int T>
    istream& operator >> (istream &in, modular<T> &x) {
        return in >> x.r;
    }


    template<typename T>
    struct poly {
        vector<T> a;

        void normalize() { // get rid of leading zeroes
            while(!a.empty() && a.back() == T(0)) {
                a.pop_back();
            }
        }

        poly(){}
        poly(T a0) : a{a0}{normalize();}
        poly(vector<T> t) : a(t){normalize();}

        poly operator += (const poly &t) {
            a.resize(max(a.size(), t.a.size()));
            for(size_t i = 0; i < t.a.size(); i++) {
                a[i] += t.a[i];
            }
            normalize();
            return *this;
        }
        poly operator -= (const poly &t) {
            a.resize(max(a.size(), t.a.size()));
            for(size_t i = 0; i < t.a.size(); i++) {
                a[i] -= t.a[i];
            }
            normalize();
            return *this;
        }
        poly operator + (const poly &t) const {return poly(*this) += t;}
        poly operator - (const poly &t) const {return poly(*this) -= t;}

        poly mod_xk(size_t k) const { // get same polynomial mod x^k
            k = min(k, a.size());
            return vector<T>(begin(a), begin(a) + k);
        }
        poly mul_xk(size_t k) const { // multiply by x^k
            poly res(*this);
            res.a.insert(begin(res.a), k, 0);
            return res;
        }
        poly div_xk(size_t k) const { // divide by x^k, dropping coefficients
            k = min(k, a.size());
            return vector<T>(begin(a) + k, end(a));
        }
        poly substr(size_t l, size_t r) const { // return mod_xk(r).div_xk(l)
            l = min(l, a.size());
            r = min(r, a.size());
            return vector<T>(begin(a) + l, begin(a) + r);
        }
        poly inv(size_t n) const { // get inverse series mod x^n
            assert(!is_zero());
            poly ans = a[0].inv();
            size_t a = 1;
            while(a < n) {
                poly C = (ans * mod_xk(2 * a)).substr(a, 2 * a);
                ans -= (ans * C).mod_xk(a).mul_xk(a);
                a *= 2;
            }
            return ans.mod_xk(n);
        }

        poly operator *= (const poly &t) {fft::mul(a, t.a); normalize(); return *this;}
        poly operator * (const poly &t) const {return poly(*this) *= t;}

        poly reverse(size_t n, bool rev = 0) const { // reverses and leaves only n terms
            poly res(*this);
            if(rev) { // If rev = 1 then tail goes to head
                res.a.resize(max(n, res.a.size()));
            }
            std::reverse(res.a.begin(), res.a.end());
            return res.mod_xk(n);
        }

        pair<poly, poly> divmod_slow(const poly &b) const { // when divisor or quotient is small
            vector<T> A(a);
            vector<T> res;
            while(A.size() >= b.a.size()) {
                res.push_back(A.back() / b.a.back());
                if(res.back() != T(0)) {
                    for(size_t i = 0; i < b.a.size(); i++) {
                        A[A.size() - i - 1] -= res.back() * b.a[b.a.size() - i - 1];
                    }
                }
                A.pop_back();
            }
            std::reverse(begin(res), end(res));
            return {res, A};
        }

        pair<poly, poly> divmod(const poly &b) const { // returns quotiend and remainder of a mod b
            if(deg() < b.deg()) {
                return {poly{0}, *this};
            }
            int d = deg() - b.deg();
            if(min(d, b.deg()) < magic) {
                return divmod_slow(b);
            }
            poly D = (reverse(d + 1) * b.reverse(d + 1).inv(d + 1)).mod_xk(d + 1).reverse(d + 1, 1);
            return {D, *this - D * b};
        }

        poly operator / (const poly &t) const {return divmod(t).first;}
        poly operator % (const poly &t) const {return divmod(t).second;}
        poly operator /= (const poly &t) {return *this = divmod(t).first;}
        poly operator %= (const poly &t) {return *this = divmod(t).second;}
        poly operator *= (const T &x) {
            for(auto &it: a) {
                it *= x;
            }
            normalize();
            return *this;
        }
        poly operator /= (const T &x) {
            for(auto &it: a) {
                it /= x;
            }
            normalize();
            return *this;
        }
        poly operator * (const T &x) const {return poly(*this) *= x;}
        poly operator / (const T &x) const {return poly(*this) /= x;}

        void print() const {
            for(auto it: a) {
                cout << it << ' ';
            }
            cout << endl;
        }
        T eval(T x) const { // evaluates in single point x
            T res(0);
            for(int i = int(a.size()) - 1; i >= 0; i--) {
                res *= x;
                res += a[i];
            }
            return res;
        }

        T& lead() { // leading coefficient
            return a.back();
        }
        int deg() const { // degree
            return a.empty() ? -inf : a.size() - 1;
        }
        bool is_zero() const { // is polynomial zero
            return a.empty();
        }
        T operator [](int idx) const {
            return idx >= (int)a.size() || idx < 0 ? T(0) : a[idx];
        }

        T& coef(size_t idx) { // mutable reference at coefficient
            return a[idx];
        }
        bool operator == (const poly &t) const {return a == t.a;}
        bool operator != (const poly &t) const {return a != t.a;}

        poly deriv() { // calculate derivative
            vector<T> res;
            for(int i = 1; i <= deg(); i++) {
                res.push_back(T(i) * a[i]);
            }
            return res;
        }
        poly integr() { // calculate integral with C = 0
            vector<T> res = {0};
            for(int i = 0; i <= deg(); i++) {
                res.push_back(a[i] / T(i + 1));
            }
            return res;
        }
        size_t leading_xk() const { // Let p(x) = x^k * t(x), return k
            if(is_zero()) {
                return inf;
            }
            int res = 0;
            while(a[res] == T(0)) {
                res++;
            }
            return res;
        }
        poly log(size_t n) { // calculate log p(x) mod x^n
            assert(a[0] == T(1));
            return (deriv().mod_xk(n) * inv(n)).integr().mod_xk(n);
        }
        poly exp(size_t n) { // calculate exp p(x) mod x^n
            if(is_zero()) {
                return T(1);
            }
            assert(a[0] == T(0));
            poly ans = T(1);
            size_t a = 1;
            while(a < n) {
                poly C = ans.log(2 * a).div_xk(a) - substr(a, 2 * a);
                ans -= (ans * C).mod_xk(a).mul_xk(a);
                a *= 2;
            }
            return ans.mod_xk(n);

        }

        poly pow_slow(size_t k, size_t n) { // if k is small
            return k ? k % 2 ? (*this * pow_slow(k - 1, n)).mod_xk(n) : (*this * *this).mod_xk(n).pow_slow(k / 2, n) : T(1);
        }
        poly pow(size_t k, size_t n) { // calculate p^k(n) mod x^n
            if(k == 0)
            {
                return {1};
            }
            if(is_zero()) {
                return *this;
            }
            if(k < magic) {
                return pow_slow(k, n);
            }
            int i = leading_xk();
            T j = a[i];
            poly t = div_xk(i) / j;
            return bpow(j, k) * (t.log(n) * T(k)).exp(n).mul_xk(i * k).mod_xk(n);
        }
        poly mulx(T x) { // component-wise multiplication with x^k
            T cur = 1;
            poly res(*this);
            for(int i = 0; i <= deg(); i++) {
                res.coef(i) *= cur;
                cur *= x;
            }
            return res;
        }
        poly mulx_sq(T x) { // component-wise multiplication with x^{k^2}
        T cur = x;
        T total = 1;
        T xx = x * x;
        poly res(*this);
        for(int i = 0; i <= deg(); i++) {
            res.coef(i) *= total;
            total *= cur;
            cur *= xx;
        }
        return res;
    }
        vector<T> chirpz_even(T z, int n) { // P(1), P(z^2), P(z^4), ..., P(z^2(n-1))
            int m = deg();
            if(is_zero()) {
                return vector<T>(n, 0);
            }
            vector<T> vv(m + n);
            T zi = z.inv();
            T zz = zi * zi;
            T cur = zi;
            T total = 1;
            for(int i = 0; i <= max(n - 1, m); i++) {
                if(i <= m) {vv[m - i] = total;}
                if(i < n) {vv[m + i] = total;}
                total *= cur;
                cur *= zz;
            }
            poly w = (mulx_sq(z) * vv).substr(m, m + n).mulx_sq(z);
            vector<T> res(n);
            for(int i = 0; i < n; i++) {
                res[i] = w[i];
            }
            return res;
        }
        vector<T> chirpz(T z, int n) { // P(1), P(z), P(z^2), ..., P(z^(n-1))
            auto even = chirpz_even(z, (n + 1) / 2);
            auto odd = mulx(z).chirpz_even(z, n / 2);
            vector<T> ans(n);
            for(int i = 0; i < n / 2; i++) {
                ans[2 * i] = even[i];
                ans[2 * i + 1] = odd[i];
            }
            if(n % 2 == 1) {
                ans[n - 1] = even.back();
            }
            return ans;
        }
        template<typename iter>
        vector<T> eval(vector<poly> &tree, int v, iter l, iter r) { // auxiliary evaluation function
            if(r - l == 1) {
                return {eval(*l)};
            } else {
                auto m = l + (r - l) / 2;
                auto A = (*this % tree[2 * v]).eval(tree, 2 * v, l, m);
                auto B = (*this % tree[2 * v + 1]).eval(tree, 2 * v + 1, m, r);
                A.insert(end(A), begin(B), end(B));
                return A;
            }
        }
        vector<T> eval(vector<T> x) { // evaluate polynomial in (x1, ..., xn)
            int n = x.size();
            if(is_zero()) {
                return vector<T>(n, T(0));
            }
            vector<poly> tree(4 * n);
            build(tree, 1, begin(x), end(x));
            return eval(tree, 1, begin(x), end(x));
        }
        template<typename iter>
        poly inter(vector<poly> &tree, int v, iter l, iter r, iter ly, iter ry) { // auxiliary interpolation function
            if(r - l == 1) {
                return {*ly / a[0]};
            } else {
                auto m = l + (r - l) / 2;
                auto my = ly + (ry - ly) / 2;
                auto A = (*this % tree[2 * v]).inter(tree, 2 * v, l, m, ly, my);
                auto B = (*this % tree[2 * v + 1]).inter(tree, 2 * v + 1, m, r, my, ry);
                return A * tree[2 * v + 1] + B * tree[2 * v];
            }
        }
    };
    template<typename T>
    poly<T> operator * (const T& a, const poly<T>& b) {
        return b * a;
    }

    template<typename T>
    poly<T> xk(int k) { // return x^k
        return poly<T>{1}.mul_xk(k);
    }

    template<typename T>
    T resultant(poly<T> a, poly<T> b) { // computes resultant of a and b
        if(b.is_zero()) {
            return 0;
        } else if(b.deg() == 0) {
            return bpow(b.lead(), a.deg());
        } else {
            int pw = a.deg();
            a %= b;
            pw -= a.deg();
            T mul = bpow(b.lead(), pw) * T((b.deg() & a.deg() & 1) ? -1 : 1);
            T ans = resultant(b, a);
            return ans * mul;
        }
    }
    template<typename iter>
    poly<typename iter::value_type> kmul(iter L, iter R) { // computes (x-a1)(x-a2)...(x-an) without building tree
        if(R - L == 1) {
            return vector<typename iter::value_type>{-*L, 1};
        } else {
            iter M = L + (R - L) / 2;
            return kmul(L, M) * kmul(M, R);
        }
    }
    template<typename T, typename iter>
    poly<T> build(vector<poly<T>> &res, int v, iter L, iter R) { // builds evaluation tree for (x-a1)(x-a2)...(x-an)
        if(R - L == 1) {
            return res[v] = vector<T>{-*L, 1};
        } else {
            iter M = L + (R - L) / 2;
            return res[v] = build(res, 2 * v, L, M) * build(res, 2 * v + 1, M, R);
        }
    }
    template<typename T>
    poly<T> inter(vector<T> x, vector<T> y) { // interpolates minimum polynomial from (xi, yi) pairs
        int n = x.size();
        vector<poly<T>> tree(4 * n);
        return build(tree, 1, begin(x), end(x)).deriv().inter(tree, 1, begin(x), end(x), begin(y), end(y));
    }
};

using namespace algebra;

typedef modular<mod> base;
typedef poly<base> polyn;

using namespace algebra;


const int MAXN=2e5+10;
vector<base> fac(MAXN);
vector<base> infac(MAXN);
void build_factorial()
{
    fac[0]=1;
    infac[0]=1;
    for(int i=1;i<MAXN;i++)
    {
        fac[i]=(fac[i-1]*(base)i);
    }
    infac[MAXN-1] = power(fac[MAXN -1], mod - 2,mod);

    for(int i= MAXN-2;i>=0;i--)
    {
        infac[i] = infac[i+1] *base(i + 1);
    }
}
base ncr(int n, int r)
{
    if(n<r)
        return 0;
    return fac[n] * infac[r]  * infac[n-r];
}





void solv()
{
    build_factorial();

    int k, q;
    cin>>k>>q;

    const int maxn = 1e5 + 10;
    polyn x;
    x.a.resize(maxn + 1);

    for(int i = 0 ;i<=maxn;i+=2)
        x.a[i] = ncr(i, i/2) * ncr(i,i/2);




    polyn power_4;
    power_4.a.resize(maxn + 1);
    power_4.a[0] = 1;

    for(int i = 1 ;i<=maxn;i++)
        power_4.a[i] = power_4.a[i-1] * base(4);



    polyn Q;
    auto l = x.inv(maxn + 1);


    Q = power_4 * l;
    Q = Q.mod_xk(maxn + 1);

    polyn P(1);

    P = P - l;



    P = P.mod_xk(maxn + 1);

    if(k == 1)
    {

        polyn A = Q.deriv() *polyn({0,1});

        polyn E = A * power_4;


        while(q--)
        {


            int n , p;
            cin>>n>>p;
            base ans = (E )[n]/ base(power(4,n,  mod));
            cout<<ans<<endl;
        }   


    }
    else
    {






        polyn D;
        D.a.resize(maxn/2 + 1);
        for(int i = 0;i<=maxn/2;i++)
            D.a[i] = P[2*i];

        D = D.pow(k-2,maxn/2 +1);
        polyn Z;
        Z.a.resize(maxn + 1);
        for(int i = 0;i<=maxn/2;i++)
            Z.a[2*i] = D[i];



        polyn left = ((Q.deriv() *Z).mod_xk(maxn+1)  * P).mul_xk(1).mod_xk(maxn+1) ;

        polyn right = ((Q *Z).mod_xk(maxn+1)  * P.deriv()  ).mul_xk(1).mod_xk(maxn+1);


        left *= power_4;
        right *= power_4;

        left = left.mod_xk(maxn+1);
        right = right.mod_xk(maxn+1);




        while(q--)
        {


            int n, p;
            cin>>n>>p;
            base ans =(left[n] + base(p-1) * right[n]) *base(mod_inv(power(4, n , mod), mod));
            cout<<ans<<endl;
        }

    }

}








void solve()
{
    int t = 1;
    // cin>>t;
    while(t--)
    {
        solv();
    }
}




signed main()
{



    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cerr.tie(NULL);

    auto clk = clock();
    // -------------------------------------Code starts here---------------------------------------------------------------------

    signed t = 1;
    // cin >> t;

    for (signed test = 1; test <= t; test++)
    {
        // cout<<"Case #"<<test<<": ";
        // cout<<endl;

        solve();
    }

    // -------------------------------------Code ends here------------------------------------------------------------------

    clk = clock() - clk;

    #ifndef ONLINE_JUDGE
    // cerr << fixed << setprecision(6) << "\nTime: " << ((float)clk) / CLOCKS_PER_SEC << "\n";
    #endif
    return 0;
}
, In this Programming Language: C++, Now tell me if this Code is compilable or not?