Consider a road consisting of several rows. Each row is divided into several rectangular tiles, and all tiles in the same row are equal. The first row contains exactly one rectangular tile. Look at the picture below which shows how the tiles are arranged.

The road is constructed as follows: 

  * the first row consists of 1 tile; 
  * then a_1 rows follow; each of these rows contains 1 tile greater than the previous row; 
  * then b_1 rows follow; each of these rows contains 1 tile less than the previous row; 
  * then a_2 rows follow; each of these rows contains 1 tile greater than the previous row; 
  * then b_2 rows follow; each of these rows contains 1 tile less than the previous row; 
  * ... 
  * then a_n rows follow; each of these rows contains 1 tile greater than the previous row; 
  * then b_n rows follow; each of these rows contains 1 tile less than the previous row. 

<image> An example of the road with n = 2, a_1 = 4, b_1 = 2, a_2 = 2, b_2 = 3. Rows are arranged from left to right. 

You start from the only tile in the first row and want to reach the last row (any tile of it). From your current tile, you can move to any tile in the next row which touches your current tile.

Calculate the number of different paths from the first row to the last row. Since it can be large, print it modulo 998244353.

Input

The first line contains one integer n (1 ≤ n ≤ 1000).

Then n lines follow. The i-th of them contains two integers a_i and b_i (1 ≤ a_i, b_i ≤ 10^5; |a_i - b_i| ≤ 5).

Additional constraint on the input: the sequence of a_i and b_i never results in a row with non-positive number of tiles.

Output

Print one integer — the number of paths from the first row to the last row, taken modulo 998244353.

Examples

Input


2
4 2
2 3


Output


850


Input


3
4 1
2 3
3 1


Output


10150


Input


8
328 323
867 868
715 718
721 722
439 435
868 870
834 834
797 796


Output


759099319
#include <bits/stdc++.h>
#pragma optimize("-O3")
const long long MOD = 998244353;
const long long INF = 1e9;
const long long INFLL = 1e18;
using namespace std;
int cx[4] = {-1, 0, 1, 0};
int cy[4] = {0, -1, 0, 1};
string Yes[2] = {"No\n", "Yes\n"};
string YES[2] = {"NO\n", "YES\n"};
string Possible[2] = {"Impossible\n", "Possible\n"};
string POSSIBLE[2] = {"IMPOSSIBLE\n", "POSSIBLE\n"};
int ok(int x, int n) { return 0 <= x && x < n; }
long long log10(long long x) {
  if (x < 10) return 1;
  return 1 + log10(x / 10);
}
long long ds(long long x) {
  if (x < 10) return x;
  return x % 10 + ds(x / 10);
}
double sqr(double x) { return x * x; }
bool inmask(int bit, int mask) { return (mask & (1 << bit)) > 0; }
void Del(vector<int> &v, int pos) {
  swap(v[pos], v[v.size() - 1]);
  v.pop_back();
}
long long g(vector<long long> &p, int pos) {
  if (ok(pos, p.size())) return p[pos];
  if (pos < 0 || p.size() == 0) return 0;
  return p.back();
}
int g(vector<int> &p, int pos) {
  if (ok(pos, p.size())) return p[pos];
  if (pos < 0 || p.size() == 0) return 0;
  return p.back();
}
long long inq(long long x, long long y) {
  if (!y) return 1 % MOD;
  long long l = inq(x, y / 2);
  if (y % 2) return l * l % MOD * x % MOD;
  return l * l % MOD;
}
long long rev(long long x) { return inq(x, MOD - 2); }
int __precomputed_combinatorics = 0;
vector<long long> __fact, __ufact, __rev;
inline void __precompute_combinatorics(int __n) {
  if (__precomputed_combinatorics >= __n) return;
  __fact.resize(__n);
  __ufact.resize(__n);
  __rev.resize(__n);
  __rev[1] = 1;
  for (int i = max(2, __precomputed_combinatorics); i < __n; i++)
    __rev[i] = MOD - __rev[MOD % i] * (MOD / i) % MOD;
  __fact[0] = 1, __ufact[0] = 1;
  for (int i = max(1, __precomputed_combinatorics); i < __n; i++)
    __fact[i] = __fact[i - 1] * i % MOD,
    __ufact[i] = __ufact[i - 1] * __rev[i] % MOD;
  __precomputed_combinatorics = __n;
}
long long fact(int x) {
  if (__precomputed_combinatorics <= x) __precompute_combinatorics(x + 1);
  return __fact[x];
}
long long cnk(int n, int k) {
  if (k < 0 || k > n) return 0;
  if (__precomputed_combinatorics <= n) __precompute_combinatorics(n + 1);
  return __fact[n] * __ufact[n - k] % MOD * __ufact[k] % MOD;
}
long long inq(long long x, long long y, long long mod) {
  if (y == 0) return 1 % mod;
  long long l = inq(x, y / 2, mod);
  if (y % 2) return l * l % mod * x % mod;
  return l * l % mod;
}
long long gcdex(long long a, long long b, long long &x, long long &y) {
  if (a == 0) {
    x = 0, y = 1;
    return b;
  }
  long long x1, y1;
  long long g = gcdex(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return g;
}
pair<long long, long long> crt(vector<long long> r, vector<long long> m) {
  int n = r.size();
  for (int i = 0; i < n; i++) r[i] %= m[i];
  long long r0 = 0, m0 = 1;
  for (int i = 0; i < n; i++) {
    long long r1 = r[i], m1 = m[i];
    if (m0 < m1) {
      swap(m0, m1);
      swap(r0, r1);
    }
    if (m0 % m1 == 0) {
      if (r0 % m1 != r1) return {0, 0};
      continue;
    }
    long long x, y;
    long long g = gcdex(m0, m1, x, y);
    long long u = m1 / g;
    if ((r0 - r1) % g != 0) return {0, 0};
    long long z = (r1 - r0) / g % u * x % u;
    r0 += z * m0;
    m0 *= u;
    if (r0 < 0) r0 += m0;
  }
  return {r0, m0};
}
struct dsu {
  vector<int> root;
  vector<int> sz;
  dsu(int _n) {
    root.resize(_n);
    iota((root).begin(), (root).end(), 0);
    sz.resize(_n, 1);
  }
  dsu() { dsu(0); }
  void Reset(int _n) {
    root.resize(_n);
    sz.resize(_n);
    for (int i = 0; i < (int)root.size(); i++) {
      root[i] = i;
      sz[i] = 1;
    }
  }
  void Reset() { Reset(root.size()); }
  int Root(int x) {
    if (x == root[x]) return x;
    return root[x] = Root(root[x]);
  }
  void Merge(int v, int u) {
    v = Root(v), u = Root(u);
    if (v == u) return;
    if (sz[v] < sz[u]) {
      sz[u] += sz[v];
      root[v] = u;
    } else {
      sz[v] += sz[u];
      root[u] = v;
    }
  }
};
struct dsu_cut {
  vector<int> root;
  vector<int> sz;
  stack<int> cuts;
  dsu_cut(int _n) {
    root.resize(_n);
    iota((root).begin(), (root).end(), 0);
    sz.resize(_n, 1);
  }
  dsu_cut() { dsu_cut(0); }
  void Cut() {
    if (!cuts.size()) return;
    int v = cuts.top();
    sz[root[v]] -= sz[v];
    root[v] = v;
    cuts.pop();
  }
  void Reset(int _n) {
    root.resize(_n);
    sz.resize(_n);
    for (int i = 0; i < (int)root.size(); i++) {
      root[i] = i;
      sz[i] = 1;
    }
  }
  void Reset() {
    if (cuts.size() < root.size()) {
      while (cuts.size()) {
        Cut();
      }
    } else {
      Reset(root.size());
    }
  }
  int Root(int x) {
    if (x == root[x]) return x;
    return Root(root[x]);
  }
  void Merge(int v, int u) {
    v = Root(v), u = Root(u);
    if (v == u) return;
    if (sz[v] < sz[u]) {
      sz[u] += sz[v];
      root[v] = u;
      cuts.push(v);
    } else {
      sz[v] += sz[u];
      root[u] = v;
      cuts.push(u);
    }
  }
};
void bfs(int v, vector<int> &dist, vector<vector<int>> &graph) {
  fill((dist).begin(), (dist).end(), -1);
  dist[v] = 0;
  vector<int> q = {v};
  for (int i = 0; i < (int)q.size(); i++) {
    for (auto u : graph[q[i]]) {
      if (dist[u] == -1) {
        dist[u] = dist[q[i]] + 1;
        q.push_back(u);
      }
    }
  }
}
vector<int> z_func(string &s) {
  vector<int> z(s.size());
  z[0] = s.size();
  int L = 0, R = 0;
  for (int i = 1; i < (int)s.size(); i++) {
    z[i] = max(0, min(z[i - L], R - i));
    while (i + z[i] < (int)s.size() && s[i + z[i]] == s[z[i]]) z[i]++;
    if (i + z[i] > R) {
      R = i + z[i];
      L = i;
    }
  }
  return z;
}
vector<int> p_func(string &s) {
  vector<int> p(s.size());
  for (int i = 1; i < (int)s.size(); i++) {
    int j = p[i - 1];
    while (j > 0 && s[i] != s[j]) j = p[j - 1];
    if (s[i] == s[j]) j++;
    p[i] = j;
  }
  return p;
}
vector<int> d1_func(string &s) {
  vector<int> d1(s.size());
  int L = 0, R = -1;
  for (int i = 0; i < (int)s.size(); i++) {
    int k = 0;
    if (i <= R) k = min(R - i + 1, d1[R - i + L]);
    while (i + k < (int)s.size() && i - k >= 0 && s[i - k] == s[i + k]) k++;
    d1[i] = k--;
    if (i + k > R) {
      L = i - k;
      R = i + k;
    }
  }
  return d1;
}
vector<int> d2_func(string &s) {
  vector<int> d2(s.size());
  int L = 0, R = -1;
  for (int i = 1; i < (int)s.size(); i++) {
    int k = 0;
    if (i <= R) k = min(R - i + 1, d2[R - i + L + 1]);
    while (i + k < (int)s.size() && i - k - 1 >= 0 && s[i - k - 1] == s[i + k])
      k++;
    d2[i] = k--;
    if (i + k > R) {
      L = i - k - 1;
      R = i + k;
    }
  }
  return d2;
}
template <class T>
void add(int pos, T x, vector<T> &fenw) {
  while (pos < (int)fenw.size()) {
    fenw[pos] += x;
    pos |= (pos + 1);
  }
}
template <class T>
T get(int pos, vector<T> &fenw) {
  long long res = 0;
  while (pos >= 0) {
    res += fenw[pos];
    pos = (pos & (pos + 1)) - 1;
  }
  return res;
}
template <class T>
vector<int> different_on_segment_offline(vector<T> a, vector<int> l,
                                         vector<int> r) {
  map<T, int> lst;
  vector<int> ans(l.size());
  vector<vector<int>> ends(a.size());
  vector<int> fenw(a.size());
  for (int i = 0; i < (int)l.size(); i++) {
    ends[r[i]].push_back(i);
  }
  for (int i = 0; i < (int)a.size(); i++) {
    if (lst.find(a[i]) != lst.end()) {
      add(lst[a[i]], -1, fenw);
    }
    lst[a[i]] = i;
    add(i, 1, fenw);
    for (auto q : ends[i]) {
      ans[q] = get(i, fenw) - get(l[q] - 1, fenw);
    }
  }
  return ans;
}
struct dcp_offine {
  int n, m;
  dsu_cut dcp;
  vector<int> ans;
  void solve(int l, int r, vector<int> &v, vector<int> &u, vector<int> &t,
             vector<int> &L, vector<int> &R) {
    if (l >= r) return;
    if (l + 1 == r) {
      if (t[l] == -1) {
        ans[l] = n - dcp.cuts.size();
      }
      if (t[l] == 1) {
        ans[l] = dcp.Root(v[l]) == dcp.Root(u[l]);
      }
      return;
    }
    int m = (l + r) / 2;
    int ss = dcp.cuts.size();
    for (int i = l; i < m; i++) {
      if (R[i] >= r) dcp.Merge(v[i], u[i]);
    }
    solve(m, r, v, u, t, L, R);
    while ((int)dcp.cuts.size() > ss) dcp.Cut();
    for (int i = r - 1; i >= m; i--) {
      if (L[i] < l) dcp.Merge(v[i], u[i]);
    }
    solve(l, m, v, u, t, L, R);
    while ((int)dcp.cuts.size() > ss) dcp.Cut();
  }
  dcp_offine(int _n, int _m, vector<int> v, vector<int> u, vector<int> t) {
    n = _n, m = _m;
    dcp.Reset(n);
    ans.resize(m, -1);
    map<pair<int, int>, int> mm;
    vector<int> L(m, INF), R(m, -INF);
    for (int i = 0; i < m; i++) {
      if (t[i] != 0) continue;
      if (v[i] > u[i]) swap(v[i], u[i]);
      if (mm.find({v[i], u[i]}) == mm.end()) {
        mm[{v[i], u[i]}] = i;
      } else {
        int t = mm[{v[i], u[i]}];
        R[t] = i;
        L[i] = t;
        mm.erase({v[i], u[i]});
      }
    }
    while (mm.size()) {
      t.push_back(0);
      ans.push_back(-1);
      L.push_back(INF);
      R.push_back(-INF);
      auto it = mm.begin();
      pair<int, int> s = (*it).first;
      int t = (*it).second;
      R[t] = m;
      L[m] = t;
      v.push_back(s.first);
      u.push_back(s.second);
      mm.erase(mm.begin());
      m++;
    }
    solve(0, m, v, u, t, L, R);
  }
};
template <class T>
struct sparse_min {
  vector<vector<T>> sp;
  vector<int> H;
  T get(int l, int r) {
    int h = H[r - l + 1];
    return min(sp[h][l], sp[h][r - (1 << h) + 1]);
  }
  sparse_min(vector<T> a) {
    int n = a.size();
    H = vector<int>(n + 1);
    for (int i = 3; i < n + 1; i++) {
      H[i] = H[i - 1] + (((i - 1) & (i - 2)) == 0);
    }
    int s = 0;
    while ((1 << s) < n) s++;
    sp = vector<vector<T>>(s, vector<T>(n));
    for (int i = 0; i < n; i++) {
      sp[0][i] = a[i];
    }
    for (int j = 1; j < s; j++) {
      for (int i = 0; i + (1 << j) - 1 < n; i++) {
        sp[j][i] = get(i, i + (1 << j) - 1);
      }
    }
  }
};
template <class T>
struct sparse_max {
  vector<vector<T>> sp;
  vector<int> H;
  T get(int l, int r) {
    int h = H[r - l + 1];
    return max(sp[h][l], sp[h][r - (1 << h) + 1]);
  }
  sparse_max(vector<T> a) {
    int n = a.size();
    H = vector<int>(n + 1);
    for (int i = 3; i < n + 1; i++) {
      H[i] = H[i - 1] + (((i - 1) & (i - 2)) == 0);
    }
    int s = 0;
    while ((1 << s) < n) s++;
    sp = vector<vector<T>>(s, vector<T>(n));
    for (int i = 0; i < n; i++) {
      sp[0][i] = a[i];
    }
    for (int j = 1; j < s; j++) {
      for (int i = 0; i + (1 << j) - 1 < n; i++) {
        sp[j][i] = get(i, i + (1 << j) - 1);
      }
    }
  }
};
struct graph_scc {
  int n;
  vector<vector<int>> graph;
  vector<vector<int>> inv_graph;
  vector<int> fr, to;
  vector<int> fn;
  vector<int> vis;
  vector<int> component;
  int col;
  void inv_dfs(int v) {
    vis[v] = 1;
    for (auto id : inv_graph[v]) {
      int u = fr[id];
      if (!vis[u]) {
        inv_dfs(u);
      }
    }
    fn.push_back(v);
  }
  void dfs(int v) {
    component[v] = col;
    for (auto id : graph[v]) {
      int u = to[id];
      if (component[u] == -1) {
        dfs(u);
      }
    }
  }
  graph_scc(int _n) {
    n = _n;
    graph = vector<vector<int>>(n);
    inv_graph = vector<vector<int>>(n);
  }
  void add_edge(int v, int u) {
    graph[v].push_back(fr.size());
    inv_graph[u].push_back(fr.size());
    fr.push_back(v);
    to.push_back(u);
  }
  vector<vector<int>> scc() {
    vis = vector<int>(n);
    component = vector<int>(n, -1);
    fn = {};
    col = 0;
    for (int i = 0; i < n; i++) {
      if (!vis[i]) {
        inv_dfs(i);
      }
    }
    reverse(fn.begin(), fn.end());
    for (auto i : fn) {
      if (component[i] == -1) {
        dfs(i);
        col++;
      }
    }
    vector<vector<int>> res(col);
    for (int i = 0; i < n; i++) {
      res[component[i]].push_back(i);
    }
    return res;
  }
};
struct graph_bridges {
  int n;
  vector<vector<int>> graph;
  vector<int> v;
  vector<int> u;
  vector<int> isbridge;
  vector<int> in, out, up;
  vector<int> color;
  vector<int> par;
  int T;
  void dfs(int V, int P, int edge_in) {
    par[V] = P;
    in[V] = up[V] = T++;
    for (auto id : graph[V]) {
      int t = v[id] + u[id] - V;
      if (in[t] == -1) {
        dfs(t, V, id);
        up[V] = min(up[V], up[t]);
      } else if (id != edge_in) {
        up[V] = min(up[V], in[t]);
      }
    }
    out[V] = T++;
  }
  void dfs_dlc(int V, int P) {
    color[V] = T;
    for (auto id : graph[V]) {
      int t = v[id] + u[id] - V;
      if (!isbridge[id] && color[t] == -1) {
        dfs_dlc(t, V);
      }
    }
  }
  graph_bridges(int _n) {
    n = _n;
    graph = vector<vector<int>>(n);
  }
  void add_edge(int V, int U) {
    graph[V].push_back(v.size());
    graph[U].push_back(v.size());
    v.push_back(V);
    u.push_back(U);
  }
  void mark_bridges() {
    in = vector<int>(n, -1);
    out = vector<int>(n, -1);
    up = vector<int>(n, -1);
    par = vector<int>(n, -1);
    isbridge = vector<int>(v.size(), 0);
    T = 0;
    for (int i = 0; i < n; i++) {
      if (in[i] == -1) {
        dfs(i, -1, -1);
      }
    }
    int m = v.size();
    for (int i = 0; i < m; i++) {
      if (par[u[i]] == v[i] && up[u[i]] == in[u[i]]) {
        isbridge[i] = 1;
      }
      if (par[v[i]] == u[i] && up[v[i]] == in[v[i]]) {
        isbridge[i] = 1;
      }
    }
  }
  vector<vector<int>> dlc() {
    mark_bridges();
    color = vector<int>(n, -1);
    T = 0;
    for (int i = 0; i < n; i++) {
      if (color[i] == -1) {
        dfs_dlc(i, -1);
        T++;
      }
    }
    vector<vector<int>> res(T);
    for (int i = 0; i < n; i++) {
      res[color[i]].push_back(i);
    }
    return res;
  }
};
struct graph_AP {
  int n;
  vector<vector<int>> graph;
  vector<int> v;
  vector<int> u;
  vector<int> isAP;
  vector<int> in, out, up;
  vector<int> par;
  vector<int> color;
  vector<int> vis;
  int T, rd;
  int maxColor;
  void dfs(int V, int P) {
    par[V] = P;
    in[V] = up[V] = T++;
    for (auto id : graph[V]) {
      int t = v[id] + u[id] - V;
      if (in[t] == -1) {
        if (P == -1) rd++;
        dfs(t, V);
        up[V] = min(up[V], up[t]);
      } else if (t != P) {
        up[V] = min(up[V], in[t]);
      }
    }
    out[V] = T++;
  }
  void dfs_blocks(int V, int P, int c) {
    vis[V] = 1;
    for (auto id : graph[V]) {
      int t = v[id] + u[id] - V;
      if (t == P) {
        continue;
      }
      if (!vis[t]) {
        if (up[t] >= in[V]) {
          maxColor++;
          color[id] = maxColor - 1;
          dfs_blocks(t, V, maxColor - 1);
        } else {
          color[id] = c;
          dfs_blocks(t, V, c);
        }
      } else {
        if (in[t] < in[V]) {
          color[id] = c;
        }
      }
    }
  }
  graph_AP(int _n) {
    n = _n;
    graph = vector<vector<int>>(n);
  }
  void add_edge(int V, int U) {
    graph[V].push_back(v.size());
    graph[U].push_back(v.size());
    v.push_back(V);
    u.push_back(U);
  }
  void mark_AP() {
    in = vector<int>(n, -1);
    out = vector<int>(n, -1);
    up = vector<int>(n, -1);
    par = vector<int>(n, -1);
    isAP = vector<int>(n, 0);
    T = 0;
    for (int i = 0; i < n; i++) {
      if (in[i] == -1) {
        rd = 0;
        dfs(i, -1);
        if (rd > 1)
          isAP[i] = 1;
        else
          isAP[i] = -1;
      }
    }
    for (int i = 0; i < n; i++) {
      if (isAP[i] == 0) {
        for (auto id : graph[i]) {
          int t = v[id] + u[id] - i;
          if (par[t] == i && in[i] <= up[t]) isAP[i] = 1;
        }
      } else {
        if (isAP[i] == -1) {
          isAP[i] = 0;
        }
      }
    }
  }
  vector<vector<int>> blocks() {
    mark_AP();
    color = vector<int>(v.size(), -1);
    vis = vector<int>(n, 0);
    maxColor = 0;
    for (int i = 0; i < n; i++) {
      if (!vis[i]) {
        dfs_blocks(i, -1, maxColor);
        maxColor++;
      }
    }
    vector<vector<int>> res = vector<vector<int>>(maxColor);
    for (int i = 0; i < (int)v.size(); i++) {
      res[color[i]].push_back(i);
    }
    vector<vector<int>> res2;
    for (int i = 0; i < (int)res.size(); i++) {
      if (res[i].size()) {
        res2.push_back(res[i]);
      }
    }
    return res2;
  }
};
int bitreverse(int x, int lg) {
  int y = 0;
  for (int i = 0; i < lg; i++) {
    y = 2 * y + (((1 << i) & x) > 0);
  }
  return y;
}
const int G = 3;
vector<int> dft(vector<int> a, int fl, int lg) {
  for (int i = 0; i < a.size(); i++) {
    int j = bitreverse(i, lg);
    if (i < j) swap(a[i], a[j]);
  }
  for (int len = 2; len <= a.size(); len <<= 1) {
    long long wlen = fl == 1 ? G : inq(G, MOD - 2);
    wlen = inq(wlen, (MOD - 1) / len);
    for (int i = 0; i < a.size(); i += len) {
      int w = 1;
      for (int j = 0; j < len / 2; j++) {
        int v = a[i + j], u = 1ll * a[i + j + len / 2] * w % MOD;
        a[i + j] = v + u >= MOD ? v + u - MOD : v + u;
        a[i + j + len / 2] = v - u < 0 ? v - u + MOD : v - u;
        w = 1ll * w * wlen % MOD;
      }
    }
  }
  return a;
}
vector<int> fft(vector<int> &a, vector<int> &b) {
  if (max(a.size(), b.size()) <= 1000) {
    vector<int> c(a.size() + b.size() - 1);
    for (int i = 0; i < a.size(); i++) {
      for (int j = 0; j < b.size(); j++) {
        c[i + j] = (c[i + j] + 1ll * a[i] * b[j]) % MOD;
      }
    }
    return c;
  }
  long long sz = a.size() + b.size() - 1;
  long long dg = 1, z = 0;
  while (dg < sz) dg *= 2, z++;
  vector<int> a0(dg), b0(dg);
  for (int i = 0; i < a.size(); i++) a0[i] = a[i];
  for (int i = 0; i < b.size(); i++) b0[i] = b[i];
  a0 = dft(a0, 1, z);
  b0 = dft(b0, 1, z);
  for (int i = 0; i < a0.size(); i++) a0[i] = 1ll * a0[i] * b0[i] % MOD;
  a0 = dft(a0, -1, z);
  int x = inq(dg, MOD - 2) % MOD;
  for (int i = 0; i < a0.size(); i++) a0[i] = 1ll * a0[i] * x % MOD;
  while (a0.size() != sz) a0.pop_back();
  return a0;
}
signed main() {
  srand(time(NULL));
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  vector<int> a(n, 100000), b(n, 99995);
  vector<int> dp = {1};
  for (int i = 0; i < n; i++) {
    vector<int> dp2(dp.size() + a[i] - b[i]);
    int Go = a[i] + b[i];
    vector<int> ways(Go + 1, 0);
    int x = dp.size();
    for (int j = 0; j <= Go; j++) {
      if (j >= Go / 2 - 5 - x && j <= Go / 2 + 5 + x) {
        ways[j] = cnk(Go, j);
      }
    }
    int fr = 0, bk = 0;
    for (int j = 0; j <= Go; j++)
      if (ways[j] == 0)
        fr++;
      else
        break;
    for (int j = Go; j >= 0; j--)
      if (ways[j] == 0)
        bk++;
      else
        break;
    vector<int> ways_mini(ways.size() - fr - bk);
    for (int j = fr, k = 0; j < ways.size() - bk; j++, k++)
      ways_mini[k] = ways[j];
    vector<int> s0 = fft(dp, ways_mini);
    vector<int> S(s0.size() + fr + bk);
    for (int j = 0, k = fr; j < s0.size(); j++, k++) S[k] = s0[j];
    for (int j = b[i], k = 0; j < S.size() - b[i]; j++, k++) dp2[k] = S[j];
    dp = dp2;
  }
  cout << accumulate((dp).begin(), (dp).end(), 0LL) % MOD << "\n";
}
