Problem: 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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
 
using namespace std;

static struct FastInput {
  static constexpr int BUF_SIZE = 1 << 20;
  char buf[BUF_SIZE];
  size_t chars_read = 0;
  size_t buf_pos = 0;
  FILE *in = stdin;
  char cur = 0;
 
  inline char get_char() {
    if (buf_pos >= chars_read) {
      chars_read = fread(buf, 1, BUF_SIZE, in);
      buf_pos = 0;
      buf[0] = (chars_read == 0 ? -1 : buf[0]);
    }
    return cur = buf[buf_pos++];
  }
 
  inline void tie(int) {}
 
  inline explicit operator bool() {
    return cur != -1;
  }
 
  inline static bool is_blank(char c) {
    return c <= ' ';
  }
 
  inline bool skip_blanks() {
    while (is_blank(cur) && cur != -1) {
      get_char();
    }
    return cur != -1;
  }
 
  inline FastInput& operator>>(char& c) {
    skip_blanks();
    c = cur;
    return *this;
  }
  
  inline FastInput& operator>>(string& s) {
    if (skip_blanks()) {
      s.clear();
      do {
        s += cur;
      } while (!is_blank(get_char()));
    }
    return *this;
  }
 
  template <typename T>
  inline FastInput& read_integer(T& n) {
    // unsafe, doesn't check that characters are actually digits
    n = 0;
    if (skip_blanks()) {
      int sign = +1;
      if (cur == '-') {
        sign = -1;
        get_char();
      }
      do {
        n += n + (n << 3) + cur - '0';
      } while (!is_blank(get_char()));
      n *= sign;
    }
    return *this;
  }
 
  template <typename T>
  inline typename enable_if<is_integral<T>::value, FastInput&>::type operator>>(T& n) {
    return read_integer(n);
  }
  
  #if !defined(_WIN32) || defined(_WIN64)
  inline FastInput& operator>>(__int128& n) {
    return read_integer(n);
  }
  #endif
 
  template <typename T>
  inline typename enable_if<is_floating_point<T>::value, FastInput&>::type operator>>(T& n) {
    // not sure if really fast, for compatibility only
    n = 0;
    if (skip_blanks()) {
      string s;
      (*this) >> s;
      sscanf(s.c_str(), "%lf", &n);
    }
    return *this;
  }
} fast_input;
 
#define cin fast_input
 
static struct FastOutput {
  static constexpr int BUF_SIZE = 1 << 20;
  char buf[BUF_SIZE];
  size_t buf_pos = 0;
  static constexpr int TMP_SIZE = 1 << 20;
  char tmp[TMP_SIZE];
  FILE *out = stdout;
 
  inline void put_char(char c) {
    buf[buf_pos++] = c;
    if (buf_pos == BUF_SIZE) {
      fwrite(buf, 1, buf_pos, out);
      buf_pos = 0;
    }
  }
 
  ~FastOutput() {
    fwrite(buf, 1, buf_pos, out);
  }
 
  inline FastOutput& operator<<(char c) {
    put_char(c);
    return *this;
  }
 
  inline FastOutput& operator<<(const char* s) {
    while (*s) {
      put_char(*s++);
    }
    return *this;
  }
 
  inline FastOutput& operator<<(const string& s) {
    for (int i = 0; i < (int) s.size(); i++) {
      put_char(s[i]);
    }
    return *this;
  }
 
  template <typename T>
  inline char* integer_to_string(T n) {
    // beware of TMP_SIZE
    char* p = tmp + TMP_SIZE - 1;
    if (n == 0) {
      *--p = '0';
    } else {
      bool is_negative = false;
      if (n < 0) {
        is_negative = true;
        n = -n;
      }
      while (n > 0) {
        *--p = (char) ('0' + n % 10);
        n /= 10;
      }
      if (is_negative) {
        *--p = '-';
      }
    }
    return p;
  }
 
  template <typename T>
  inline typename enable_if<is_integral<T>::value, char*>::type stringify(T n) {
    return integer_to_string(n);
  }
 
  #if !defined(_WIN32) || defined(_WIN64)
  inline char* stringify(__int128 n) {
    return integer_to_string(n);
  }
  #endif
 
  template <typename T>
  inline typename enable_if<is_floating_point<T>::value, char*>::type stringify(T n) {
    sprintf(tmp, "%.17f", n);
    return tmp;
  }
 
  template <typename T>
  inline FastOutput& operator<<(const T& n) {
    auto p = stringify(n);
    for (; *p != 0; p++) {
      put_char(*p);
    }
    return *this;
  }
} fast_output;

// here puts define
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define rint register int
#define rll register ll 
#define pii pair<int, int>
#define pll pair<ll, ll>
//#define p1 first
//#define p2 second
#define fors(i, a, b) for (ll i = (a); i <= (b); ++i)
#define _fors(i, a, b) for (ll i = (a); i >= (b); --i)
#define mp(a, b) make_pair(a, b)
#define mt(a, b, c) make_tuple(a, b, c)
#define mem(A, b) memset(A, b, sizeof(A))
#define all(X) (X).begin(), (X).end()
#define pb push_back
#define eb emplace_back
#define cout fast_output
#define endl '\n'

const int mod = 998244353;
const int maxn = 1e6 + 5;

inline int add(int a, int b) {
  return (((a + b) % mod) + mod) % mod;
}

inline int mul(int a, int b) {
  return (((1LL * a * b) % mod) + mod) % mod;
}

inline int qpow(int a, int p) {
  int ret = 1;
  while (p) {
    if (p & 1) ret = mul(ret, a);
    a = mul(a, a);
    p >>= 1;
  }
  return ret;
}

int cda[4*maxn], cdb[4*maxn];
int res[4*maxn];

inline void NTT(int* a, int a_size, bool inverse) {
  int n = a_size;
  // 原地快速bit reversal
  for(int i = 0, j = 0; i < n; i++) {
    if(j > i) swap(a[i], a[j]);
    int k = n;
    while(j & (k >>= 1)) j &= ~k;
    j |= k;
  }

  int root = inverse ? qpow(3, mod-2) : 3;

  for(int step = 1; step < n; step <<= 1) {
    int alpha = (mod-1) / step / 2;
    // 为求高效，我们并不是依次执行各个完整的DFT合并，而是枚举下标k
    // 对于一个下标k，执行所有DFT合并中该下标对应的蝴蝶操作，即通过E[k]和O[k]计算X[k]
    int omega = qpow(root, alpha), omegak = 1;
    for(int k = 0; k < step; k++) {
      // 计算omega^k. 这个方法效率低，但如果用每次乘omega的方法递推会有精度问题。
      // 有更快更精确的递推方法，为了清晰起见这里略去
      for(int Ek = k; Ek < n; Ek += step << 1) { // Ek是某次DFT合并中E[k]在原始序列中的下标
        int Ok = Ek + step; // Ok是该DFT合并中O[k]在原始序列中的下标
        int t = mul(a[Ok], omegak); // 蝴蝶操作：x1 * omega^k
        a[Ok] = add(a[Ek], -t);  // 蝴蝶操作：y1 = x0 - t
        a[Ek] = add(a[Ek], t);         // 蝴蝶操作：y0 = x0 + t
      }
      omegak = mul(omegak, omega);
    }
  }

  if(inverse) {
    int invn = qpow(n, mod - 2);
    fors(i, 0, n-1) a[i] = mul(a[i], invn);
  }

  return ;
}

// 用FFT实现的快速多项式乘法
inline int NTT_mul(int* v1, int v1_size, int* v2, int v2_size) {
  int s1 = v1_size, s2 = v2_size, S = 2;
  while(S < s1 + s2) S <<= 1;
  fors(i, 0, S-1) cda[i] = 0, cdb[i] = 0;
  for(int i = 0; i < s1; i++) cda[i] = v1[i];
  NTT(cda, S, false);
  for(int i = 0; i < s2; i++) cdb[i] = v2[i];
  NTT(cdb, S, false);
  for(int i = 0; i < S; i++) cda[i] = mul(cda[i], cdb[i]);
  NTT(cda, S, true);
  for(int i = 0; i < s1 + s2 - 1; i++) res[i] = cda[i]; // 虚部均为0
  return s1 + s2 - 1;
}

int n;
int a[maxn], b[maxn], s[maxn], t[maxn], inv[maxn];
int tab[maxn], itab[maxn];
int m;

void solve() {
  inv[1] = 1, tab[0] = 1, itab[0] = 1;
  fors(i, 2, 2e5 + 5) inv[i]= mul(-mod/i, inv[mod%i]);
  fors(i, 1, 2e5 + 5) tab[i] = mul(tab[i-1], i);
  fors(i, 1, 2e5 + 5) itab[i] = mul(itab[i-1], inv[i]); 
  cin >> n;
  fors(i, 1, n) cin >> a[i] >> b[i];
  s[0] = 1;
  m = 0;
  fors(i, 1, n) {
    fors(j, 0, a[i] + m - b[i] + m) {
      t[j] = j + b[i] - m <= a[i] + b[i] && j + b[i] - m >= 0 ? mul(tab[a[i] + b[i]], mul(itab[j + b[i] - m], itab[a[i] + m - j])) : 0;
    }
    int tmp = NTT_mul(s, m + 1, t, a[i] + m - b[i] + m + 1);
    fors(j, 0, m + a[i] - b[i]) s[j] = res[j + m];
    m += a[i] - b[i];
    // fors(j, 0, s_siz - 1) cout << s[j] << ' ';
    // cout << endl;
  }
  int ret = 0;
  fors(i, 0, m) ret = add(ret, s[i]);
  cout << ret << endl;
  return ;
}

signed main() {
  #ifdef Sakuyalove
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
  #endif
  ios::sync_with_stdio(false);
  cin.tie(0);
  int start_time = clock();

  int T = 1;
  // cin >> T;
  while (T--) {

    solve();
  }
  #ifdef Sakuyalove
    cout << "time = " << clock() - start_time << endl;
  #endif
  return 0;
}