結果

問題 No.2605 Pickup Parentheses
ユーザー fastmathfastmath
提出日時 2024-01-12 23:33:33
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 17,765 bytes
コンパイル時間 3,296 ms
コンパイル使用メモリ 176,896 KB
実行使用メモリ 24,592 KB
最終ジャッジ日時 2024-09-28 00:19:18
合計ジャッジ時間 10,412 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 3 ms
6,940 KB
testcase_04 AC 3 ms
6,944 KB
testcase_05 AC 3 ms
6,940 KB
testcase_06 AC 5 ms
6,944 KB
testcase_07 AC 4 ms
6,944 KB
testcase_08 AC 5 ms
6,940 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 4 ms
6,940 KB
testcase_11 AC 3 ms
6,944 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 AC 160 ms
16,880 KB
testcase_19 AC 79 ms
10,536 KB
testcase_20 AC 16 ms
6,944 KB
testcase_21 AC 10 ms
6,940 KB
testcase_22 AC 6 ms
6,940 KB
testcase_23 AC 167 ms
17,220 KB
testcase_24 AC 16 ms
6,940 KB
testcase_25 AC 188 ms
20,396 KB
testcase_26 AC 193 ms
20,388 KB
testcase_27 AC 160 ms
16,508 KB
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 AC 51 ms
11,340 KB
testcase_39 AC 17 ms
6,940 KB
testcase_40 AC 107 ms
16,848 KB
testcase_41 AC 104 ms
19,736 KB
testcase_42 AC 136 ms
18,872 KB
testcase_43 AC 29 ms
7,808 KB
testcase_44 AC 31 ms
9,076 KB
testcase_45 AC 7 ms
6,948 KB
testcase_46 AC 14 ms
6,940 KB
testcase_47 AC 3 ms
6,944 KB
testcase_48 WA -
testcase_49 WA -
testcase_50 WA -
testcase_51 WA -
testcase_52 WA -
testcase_53 WA -
testcase_54 WA -
testcase_55 WA -
testcase_56 WA -
testcase_57 WA -
testcase_58 AC 214 ms
24,592 KB
testcase_59 AC 183 ms
19,740 KB
testcase_60 AC 219 ms
19,644 KB
testcase_61 AC 202 ms
20,060 KB
testcase_62 AC 206 ms
19,980 KB
testcase_63 AC 209 ms
20,136 KB
testcase_64 AC 217 ms
20,880 KB
testcase_65 AC 185 ms
19,620 KB
testcase_66 AC 241 ms
23,312 KB
testcase_67 AC 204 ms
20,100 KB
testcase_68 WA -
testcase_69 AC 2 ms
6,944 KB
testcase_70 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <fstream>
#include <array>
#include <functional>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define x first
#define y second
#define Time (double)clock()/CLOCKS_PER_SEC
#define munq(a) sort(all(a)); a.resize(unique(all(a))-a.begin())
#define sz(a) ((int)a.size())

#ifdef LOCAL
#define debug(x) do { cout << #x << ": " << x << endl; } while(0)
#define debug2(x, y) do { std::cerr << #x << ", " << #y << ": " << x << ", " << y << endl; } while (0)
#define debug3(x, y, z) do {std::cerr << #x << ", " << #y << ", " << #z << ": " << x << ", " << y << ", " << z << endl; } while(0)
#else
#define debug(x)
#define debug2(x, y) 
#define debug3(x, y, z) 
#endif

#define FORI(i,a,b) for (int i = (a); i < (b); ++i)
#define FOR(i,a) FORI(i,0,a)
#define ROFI(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define ROF(i,a) ROFI(i,0,a)
#define rep(a) FOR(_,a)
#define each(a,x) for (auto& a: x)
#define FORN(i, n) FORI(i, 1, n + 1)

using vi = vector<int>;
template <typename T>
std::istream& operator >>(std::istream& input, std::pair <T, T> & data)
{
    input >> data.x >> data.y;
    return input;
}
template <typename T>
std::istream& operator >>(std::istream& input, std::vector<T>& data)
{
    for (T& x : data)
        input >> x;
    return input;
}
template <typename T>
std::ostream& operator <<(std::ostream& output, const pair <T, T> & data)
{
    output << "(" << data.x << "," << data.y << ")";
    return output;
}
template <typename T>
std::ostream& operator <<(std::ostream& output, const std::vector<T>& data)
{
    for (const T& x : data)
        output << x << " ";
    return output;
}
ll div_up(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll div_down(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down 
ll math_mod(ll a, ll b) { return a - b * div_down(a, b); }
#define tcT template<class T
#define tcTU tcT, class U
tcT> using V = vector<T>; 
tcT> bool ckmin(T& a, const T& b) {
    return b < a ? a = b, 1 : 0; 
} // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
    return a < b ? a = b, 1 : 0; 
}
tcT> vector <T> presum(vector <T> &a) {
    vector <T> p(a.size() + 1);
    FOR (i, a.size()) {
        p[i + 1] = p[i] + a[i];
    }   
    return p;
}
tcT> vector <T> sufsum(vector <T> &a) {
    vector <T> p(a.size() + 1);
    for (int i = (int)a.size() - 1; i >= 0; --i) {
        p[i] = p[i + 1] + a[i];
    }
    return p;
}
ll gcd(ll a, ll b) {
    while (b) {
        tie(a, b) = mp(b, a % b);
    }
    return a;
}
int Bit(int mask, int bit) { return (mask >> bit) & 1; }

template<int MOD, int RT> struct mint {
    static const int mod = MOD;
    static constexpr mint rt() { return RT; } // primitive root for FFT
    int v; explicit operator int() const { return v; } // explicit -> don't silently convert to int
    mint() { v = 0; }
    mint(ll _v) { v = (int)((-MOD < _v && _v < MOD) ? _v : _v % MOD);
        if (v < 0) v += MOD; }
    friend bool operator==(const mint& a, const mint& b) { 
        return a.v == b.v; }
    friend bool operator!=(const mint& a, const mint& b) { 
        return !(a == b); }
    friend bool operator<(const mint& a, const mint& b) { 
        return a.v < b.v; }
    friend string ts(mint a) { return to_string(a.v); }

    mint& operator+=(const mint& m) { 
        if ((v += m.v) >= MOD) v -= MOD; 
        return *this; }
    mint& operator-=(const mint& m) { 
        if ((v -= m.v) < 0) v += MOD; 
        return *this; }
    mint& operator*=(const mint& m) { 
        v = (int)((ll)v*m.v%MOD); return *this; }
    mint& operator/=(const mint& m) { return (*this) *= inv(m); }
    friend mint pow(mint a, ll p) {
        mint ans = 1; assert(p >= 0);
        for (; p; p /= 2, a *= a) if (p&1) ans *= a;
        return ans; }
    mint & operator ^=(const int &p) { return (*this) = pow(this, p); }

    friend mint inv(const mint& a) { 
        return pow(a,MOD-2); }
        
    mint operator-() const { return mint(-v); }
    mint& operator++() { return *this += 1; }
    mint& operator--() { return *this -= 1; }
    friend mint operator+(mint a, const mint& b) { return a += b; }
    friend mint operator-(mint a, const mint& b) { return a -= b; }
    friend mint operator*(mint a, const mint& b) { return a *= b; }
    friend mint operator/(mint a, const mint& b) { return a /= b; }
    friend mint operator^(mint a, const int p) { return pow(a, p); }
};

const int MOD = 998244353;

typedef mint<MOD,5> mi; // 5 is primitive root for both common mods
typedef vector<mi> vmi;

std::ostream& operator << (std::ostream& o, const mi& a)
{
    cout << a.v;
    return o;
}

vector<vmi> scmb; // small combinations
void genComb(int SZ) {
    scmb.assign(SZ,vmi(SZ)); scmb[0][0] = 1;
    FORI(i,1,SZ) FOR(j,i+1) 
        scmb[i][j] = scmb[i-1][j]+(j?scmb[i-1][j-1]:0);
}
 
vmi invs, fac, ifac; // make sure to convert to LL before doing any multiplications ...
void genFac(int SZ) {
    invs.resize(SZ), fac.resize(SZ), ifac.resize(SZ); 
    invs[1] = fac[0] = ifac[0] = 1; 
    FORI(i,2,SZ) invs[i] = mi(-(ll)MOD/i*(int)invs[MOD%i]);
    FORI(i,1,SZ) {
        fac[i] = fac[i-1]*i;
        ifac[i] = ifac[i-1]*invs[i];
    }
}
mi comb(int a, int b) {
    if (a < b || b < 0) return 0;
    assert(a < fac.size());
    return fac[a]*ifac[b]*ifac[a-b];
}
mi partNonNegative(int a, int b) {
    assert(a >= 0);
    if (a == 0 && b == 0) {
        return 1;
    }
    else {
        return comb(a + b - 1, b - 1);
    }
}
mi partPositive(int a, int b) {
    assert(a >= 0);
    if (a == 0 && b == 0) {
        return 1;
    }
    else {
        return comb(a - 1, b - 1);
    }
}

const int md = 998244353;
 
namespace faq{
 
inline void add(int &x, int y) {
  x += y;
  if (x >= md) {
    x -= md;
  }
}
 
inline void sub(int &x, int y) {
  x -= y;
  if (x < 0) {
    x += md;
  }
}
 
inline int mul(int x, int y) {
  return (long long) x * y % md;
}
 
inline int power(int x, int y) {
  int res = 1;
  for (; y; y >>= 1, x = mul(x, x)) {
    if (y & 1) {
      res = mul(res, x);
    }
  }
  return res;
}
 
inline int inv(int a) {
  a %= md;
  if (a < 0) {
    a += md;
  }
  int b = md, u = 0, v = 1;
  while (a) {
    int t = b / a;
    b -= t * a;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  if (u < 0) {
    u += md;
  }
  return u;
}
 
namespace ntt {
int base = 1, root = -1, max_base = -1;
vector<int> rev = {0, 1}, roots = {0, 1};
 
void init() {
  int temp = md - 1;
  max_base = 0;
  while (temp % 2 == 0) {
    temp >>= 1;
    ++max_base;
  }
  root = 2;
  while (true) {
    if (power(root, 1 << max_base) == 1 && power(root, 1 << max_base - 1) != 1) {
      break;
    }
    ++root;
  }
}

void ensure_base(int nbase) {
  if (max_base == -1) {
    init();
  }
  if (nbase <= base) {
    return;
  }
  assert(nbase <= max_base);
  rev.resize(1 << nbase);
  for (int i = 0; i < 1 << nbase; ++i) {
    rev[i] = rev[i >> 1] >> 1 | (i & 1) << nbase - 1;
  }
  roots.resize(1 << nbase);
  while (base < nbase) {
    int z = power(root, 1 << max_base - 1 - base);
    for (int i = 1 << base - 1; i < 1 << base; ++i) {
      roots[i << 1] = roots[i];
      roots[i << 1 | 1] = mul(roots[i], z);
    }
    ++base;
  }
}
 
void dft(vector<int> &a) {
  int n = a.size(), zeros = __builtin_ctz(n);
  ensure_base(zeros);
  int shift = base - zeros;
  for (int i = 0; i < n; ++i) {
    if (i < rev[i] >> shift) {
      swap(a[i], a[rev[i] >> shift]);
    }
  }
  for (int i = 1; i < n; i <<= 1) {
    for (int j = 0; j < n; j += i << 1) {
      for (int k = 0; k < i; ++k) {
        int x = a[j + k], y = mul(a[j + k + i], roots[i + k]);
        a[j + k] = (x + y) % md;
        a[j + k + i] = (x + md - y) % md;
      }
    }
  }
}
 
vector<int> multiply(vector<int> a, vector<int> b) {
  int need = a.size() + b.size() - 1, nbase = 0;
  while (1 << nbase < need) {
    ++nbase;
  }
  ensure_base(nbase);
  int sz = 1 << nbase;
  a.resize(sz);
  b.resize(sz);
  bool equal = a == b;
  dft(a);
  if (equal) {
    b = a;
  } else {
    dft(b);
  }
  int inv_sz = inv(sz);
  for (int i = 0; i < sz; ++i) {
    a[i] = mul(mul(a[i], b[i]), inv_sz);
  }
  reverse(a.begin() + 1, a.end());
  dft(a);
  a.resize(need);
  return a;
}
 
vector<int> inverse(vector<int> a) {
  int n = a.size(), m = n + 1 >> 1;
  if (n == 1) {
    return vector<int>(1, inv(a[0]));
  } else {
    vector<int> b = inverse(vector<int>(a.begin(), a.begin() + m));
    int need = n << 1, nbase = 0;
    while (1 << nbase < need) {
      ++nbase;
    }
    ensure_base(nbase);
    int sz = 1 << nbase;
    a.resize(sz);
    b.resize(sz);
    dft(a);
    dft(b);
    int inv_sz = inv(sz);
    for (int i = 0; i < sz; ++i) {
      a[i] = mul(mul(md + 2 - mul(a[i], b[i]), b[i]), inv_sz);
    }
    reverse(a.begin() + 1, a.end());
    dft(a);
    a.resize(n);
    return a;
  }
}
}
 
using ntt::multiply;
using ntt::inverse;
 
vector<int>& operator += (vector<int> &a, const vector<int> &b) {
  if (a.size() < b.size()) {
    a.resize(b.size());
  }
  for (int i = 0; i < b.size(); ++i) {
    add(a[i], b[i]);
  }
  return a;
}
 
vector<int> operator + (const vector<int> &a, const vector<int> &b) {
  vector<int> c = a;
  return c += b;
}
 
vector<int>& operator -= (vector<int> &a, const vector<int> &b) {
  if (a.size() < b.size()) {
    a.resize(b.size());
  }
  for (int i = 0; i < b.size(); ++i) {
    sub(a[i], b[i]);
  }
  return a;
}
 
vector<int> operator - (const vector<int> &a, const vector<int> &b) {
  vector<int> c = a;
  return c -= b;
}
 
vector<int>& operator *= (vector<int> &a, const vector<int> &b) {
  if (min(a.size(), b.size()) < 128) {
    vector<int> c = a;
    a.assign(a.size() + b.size() - 1, 0);
    for (int i = 0; i < c.size(); ++i) {
      for (int j = 0; j < b.size(); ++j) {
        add(a[i + j], mul(c[i], b[j]));
      }
    }
  } else {
    a = multiply(a, b);
  }
  return a;
}
 
vector<int> operator * (const vector<int> &a, const vector<int> &b) {
  vector<int> c = a;
  return c *= b;
}
 
vector<int>& operator /= (vector<int> &a, const vector<int> &b) {
  int n = a.size(), m = b.size();
  if (n < m) {
    a.clear();
  } else {
    vector<int> c = b;
    reverse(a.begin(), a.end());
    reverse(c.begin(), c.end());
    c.resize(n - m + 1);
    a *= inverse(c);
    a.erase(a.begin() + n - m + 1, a.end());
    reverse(a.begin(), a.end());
  }
  return a;
}
 
vector<int> operator / (const vector<int> &a, const vector<int> &b) {
  vector<int> c = a;
  return c /= b;
}
 
vector<int>& operator %= (vector<int> &a, const vector<int> &b) {
  int n = a.size(), m = b.size();
  if (n >= m) {
    vector<int> c = (a / b) * b;
    a.resize(m - 1);
    for (int i = 0; i < m - 1; ++i) {
      sub(a[i], c[i]);
    }
  }
  return a;
}
 
vector<int> operator % (const vector<int> &a, const vector<int> &b) {
  vector<int> c = a;
  return c %= b;
}
 
vector<int> derivative(const vector<int> &a) {
  int n = a.size();
  vector<int> b(n - 1);
  for (int i = 1; i < n; ++i) {
    b[i - 1] = mul(a[i], i);
  }
  return b;
}
 
vector<int> primitive(const vector<int> &a) {
  int n = a.size();
  vector<int> b(n + 1), invs(n + 1);
  for (int i = 1; i <= n; ++i) {
    invs[i] = i == 1 ? 1 : mul(md - md / i, invs[md % i]);
    b[i] = mul(a[i - 1], invs[i]);
  }
  return b;
}
 
vector<int> logarithm(const vector<int> &a) {
  vector<int> b = primitive(derivative(a) * inverse(a));
  b.resize(a.size());
  return b;
}
 
vector<int> exponent(const vector<int> &a) {
  vector<int> b(1, 1);
  while (b.size() < a.size()) {
    vector<int> c(a.begin(), a.begin() + min(a.size(), b.size() << 1));
    add(c[0], 1);
    vector<int> old_b = b;
    b.resize(b.size() << 1);
    c -= logarithm(b);
    c *= old_b;
    for (int i = b.size() >> 1; i < b.size(); ++i) {
      b[i] = c[i];
    }
  }
  b.resize(a.size());
  return b;
}
 
vector<int> power(const vector<int> &a, int m) {
  int n = a.size(), p = -1;
  vector<int> b(n);
  for (int i = 0; i < n; ++i) {
    if (a[i]) {
      p = i;
      break;
    }
  }
  if (p == -1) {
    b[0] = !m;
    return b;
  }
  if ((long long) m * p >= n) {
    return b;
  }
  int mu = power(a[p], m), di = inv(a[p]);
  vector<int> c(n - m * p);
  for (int i = 0; i < n - m * p; ++i) {
    c[i] = mul(a[i + p], di);
  }
  c = logarithm(c);
  for (int i = 0; i < n - m * p; ++i) {
    c[i] = mul(c[i], m);
  }
  c = exponent(c);
  for (int i = 0; i < n - m * p; ++i) {
    b[i + m * p] = mul(c[i], mu);
  }
  return b;
}
 
vector<int> sqrt(const vector<int> &a) {
  vector<int> b(1, 1);
  while (b.size() < a.size()) {
    vector<int> c(a.begin(), a.begin() + min(a.size(), b.size() << 1));
    vector<int> old_b = b;
    b.resize(b.size() << 1);
    c *= inverse(b);
    for (int i = b.size() >> 1; i < b.size(); ++i) {
      b[i] = mul(c[i], md + 1 >> 1);
    }
  }
  b.resize(a.size());
  return b;
}
 
vector<int> multiply_all(int l, int r, vector<vector<int>> &all) {
  if (l > r) {
    return vector<int>();
  } else if (l == r) {
    return all[l];
  } else {
    int y = l + r >> 1;
    return multiply_all(l, y, all) * multiply_all(y + 1, r, all);
  }
}
 
vector<int> evaluate(const vector<int> &f, const vector<int> &x) {
  int n = x.size();
  if (!n) {
    return vector<int>();
  }
  vector<vector<int>> up(n * 2);
  for (int i = 0; i < n; ++i) {
    up[i + n] = vector<int>{(md - x[i]) % md, 1};
  }
  for (int i = n - 1; i; --i) {
    up[i] = up[i << 1] * up[i << 1 | 1];
  }
  vector<vector<int>> down(n * 2);
  down[1] = f % up[1];
  for (int i = 2; i < n * 2; ++i) {
    down[i] = down[i >> 1] % up[i];
  }
  vector<int> y(n);
  for (int i = 0; i < n; ++i) {
    y[i] = down[i + n][0];
  }
  return y;
}
 
vector<int> interpolate(const vector<int> &x, const vector<int> &y) {
  int n = x.size();
  vector<vector<int>> up(n * 2);
  for (int i = 0; i < n; ++i) {    up[i + n] = vector<int>{(md - x[i]) % md, 1};
  }
  for (int i = n - 1; i; --i) {
    up[i] = up[i << 1] * up[i << 1 | 1];
  }
  vector<int> a = evaluate(derivative(up[1]), x);
  for (int i = 0; i < n; ++i) {
    a[i] = mul(y[i], inv(a[i]));
  }
  vector<vector<int>> down(n * 2);
  for (int i = 0; i < n; ++i) {
    down[i + n] = vector<int>(1, a[i]);
  }
  for (int i = n - 1; i; --i) {
    down[i] = down[i << 1] * up[i << 1 | 1] + down[i << 1 | 1] * up[i << 1];
  }
  return down[1];
}

vi composition(vi p, vi q) {
    vi ans;
    vi cur = {1};
    each (x, p) {
        ans += vi({x}) * cur;
        cur *= q;
    }
    return ans;
}

vi multiply_all(V <vi> &all) {
    return multiply_all(0,(int)all.size()-1,all);
}

pair <vi,vi> sum_all(int l, int r, V <pair<vi,vi>> &all) {
    if (l == r) {
        return all[l];
    }
    int m = (l + r) / 2;
    auto [a, b] = sum_all(l, m, all);
    auto [c, d] = sum_all(m + 1, r, all);
    return {a * d + b * c, b * d};
}

pair<vi,vi> sum_all(V <pair<vi,vi>> &all) {
    return sum_all(0,(int)all.size()-1,all);
}

vi substitute_exp(vi a) {
    int n = a.size();
    V <pair <vi, vi> > w;
    FOR (i, n) {
        vi nom = {a[i]};
        vi den = {1,mul(i,998244352)};
        w.app({nom, den});
    }
    auto [u,v] = sum_all(w);
    vi q = u*inverse(v);
    int f = 1;
    FOR(i, n) {
        if (i) {
            f = mul(f,i);
        }
        q[i] = mul(q[i],inv(f));
    }
    return q;
}

vi binomial_representation(vi a) {
  int n = sz(a);
  vi po(n);
  iota(all(po), 0);
  vi val = evaluate(a, po);
  for (int i = 2; i < n; ++i) {
    val[i] = (mi(val[i])*ifac[i]).v;
  }
  vi invexp(n);
  FOR (i, n) {
    invexp[i] = ifac[i].v;
    if (i & 1) {
      invexp[i] = mi(-invexp[i]).v;
    }
  }
  vi ans = val * invexp;
  ans.resize(n);
  FOR (i, n) {
    ans[i] = (mi(ans[i])*fac[i]).v;
  }
  return ans;
}
vi binomial_representation_by_values(vi val) { //val is values of poly of degree n at 0...n
  int n = sz(val);
  for (int i = 2; i < n; ++i) {
    val[i] = (mi(val[i])*ifac[i]).v;
  }
  vi invexp(n);
  FOR (i, n) {
    invexp[i] = ifac[i].v;
    if (i & 1) {
      invexp[i] = mi(-invexp[i]).v;
    }
  }
  vi ans = val * invexp;
  ans.resize(n);
  FOR (i, n) {
    ans[i] = (mi(ans[i])*fac[i]).v;
  }
  return ans;
}
vi get_poly_by_binomial_representation_slow(vi bin) {
  int n = sz(bin);
    vi check(n);
    FOR (i, n) {
      V <vi> bi;
      bi.app({1});
      FOR (j, i) {
        bi.app({mi(-j).v, 1});
      }
      vi b = multiply_all(bi);
      each (e, b) {
        e = (mi(e)/fac[i]).v;
      }
      /*
      debug2(i, b);
      each (e, b) {
        cout << mi(e)*6 << ' ';
      }
      cout << endl;
      */
      FOR (j, sz(b)) {
        check[j] = mi(check[j] + b[j]*bin[i]).v;
      }
    }
    return check;
}

}
signed main() {
    #ifdef LOCAL
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    int n, m;
    cin >> n >> m;
    auto cat = [&] (int n) {
        return comb(2 * n, n) / mi(n + 1);
    };
    genFac(2 * n + 1);
    n /= 2;
    V <vi> al;
    rep (m) {
        int l, r; cin >> l >> r;
        int le = (r - l + 1) / 2;
        vi add(le + 1);
        add[0] = 1;
        add.back() = (mi(-1) * cat(le)).v;
        al.app(add);
    }
    auto res = faq::multiply_all(al);
    mi ans = 0;
    for (int l = 0; l <= n && l < sz(res); ++l) {
        int os = n - l;
        ans += cat(os) * res[l];
    }
    cout << ans << endl;
}
0