#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
const long long INF = std::numeric_limits<long long>::max() / 2 - 100000000;
const long long INF2 = std::numeric_limits<long long>::max() / 2 - 100000000;
const long double pi = acos(-1);
constexpr long long MOD = 998244353;
long long my_gcd(long long a, long long b) {
  if (b == 0) return a;
  return my_gcd(b, a % b);
}
long long my_gcd_ext(long long a, long long b, long long& x, long long& y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long tempo = my_gcd_ext(b, a % b, y, x);
  y -= (a / b) * x;
  return tempo;
}
long long my_invmod(long long a, long long M) {
  long long x = 0, y = 0;
  long long memo = my_gcd_ext(a, M, x, y);
  assert(memo == 1LL);
  x %= M;
  if (x < 0) x += M;
  return x;
}
long long my_pow(long long N, long long a, long long M) {
  long long tempo;
  if (a == 0) {
    return 1;
  } else {
    if (a % 2 == 0) {
      tempo = my_pow(N, a / 2, M);
      return (tempo * tempo) % M;
    } else {
      tempo = my_pow(N, a - 1, M);
      return (tempo * N) % M;
    }
  }
}
long long my_pow(long long N, long long a) {
  long long tempo;
  if (a == 0) {
    return 1;
  } else {
    if (a % 2 == 0) {
      tempo = my_pow(N, a / 2);
      return (tempo * tempo);
    } else {
      tempo = my_pow(N, a - 1);
      return (tempo * N);
    }
  }
}
long long my_combination(long long N, long long a, long long M) {
  if (N < a) return 0;
  long long answer = 1;
  for (long long i = 0; i < (a); i++) {
    answer *= (N - i);
    answer %= M;
  }
  for (long long i = 0; i < (a); i++) {
    answer *= my_pow(i + 1, M - 2, M);
    answer %= M;
  }
  return answer;
}
void my_combination_table(long long N, long long M, vector<long long>& v) {
  v.assign(N + 1, 1);
  for (long long i = 1; i <= N; i++) {
    v.at(i) = v.at(i - 1) * (N - (i - 1LL));
    v.at(i) %= M;
    v.at(i) *= my_pow(i, M - 2, M);
    v.at(i) %= M;
  }
}
void my_combination_table2(long long N, long long M, vector<long long>& v) {
  v.at(0) = 1;
  for (long long i = 1; i < (long long)v.size(); i++) {
    v.at(i) = v.at(i - 1) * (N + i);
    v.at(i) %= M;
    v.at(i) *= my_pow(i, M - 2, M);
    v.at(i) %= M;
  }
}
long long factorial(long long x, vector<long long>& dp) {
  if ((long long)dp.size() <= x) {
    long long n = dp.size();
    for (long long i = 0; i < (x + 1 - n); i++) {
      dp.push_back(0);
    }
  }
  if (x == 0) return dp.at(x) = 1;
  if (dp.at(x) != -1 && dp.at(x) != 0) return dp.at(x);
  return dp.at(x) = x * factorial(x - 1, dp);
}
long long factorial2(long long x, long long M, vector<long long>& dp) {
  if ((long long)dp.size() <= x) {
    long long n = dp.size();
    for (long long i = 0; i < (x + 1 - n); i++) {
      dp.push_back(0);
    }
  }
  if (x == 0) return dp.at(x) = 1;
  if (dp.at(x) != -1 && dp.at(x) != 0) return dp.at(x);
  long long tempo = (x * factorial2(x - 1, M, dp));
  tempo %= M;
  return dp.at(x) = tempo;
}
long long factorial_inverse(long long x, long long M, vector<long long>& dp) {
  if ((long long)dp.size() <= x) {
    long long n = dp.size();
    for (long long i = 0; i < (x + 1 - n); i++) {
      dp.push_back(0);
    }
  }
  if (x == 0) return dp.at(x) = 1;
  if (dp.at(x) != -1 && dp.at(x) != 0) return dp.at(x);
  return dp.at(x) = (my_pow(x, M - 2, M) * factorial_inverse(x - 1, M, dp)) % M;
}
long long my_combination2(long long N, long long a, long long M,
                          vector<long long>& dp_factorial,
                          vector<long long>& dp_factorial_inverse) {
  if ((long long)dp_factorial.size() <= N) {
    factorial2(N, M, dp_factorial);
  }
  if ((long long)dp_factorial_inverse.size() <= N) {
    factorial_inverse(N, M, dp_factorial_inverse);
  }
  if (N < a) return 0;
  long long answer = 1;
  answer *= dp_factorial.at(N);
  answer %= M;
  answer *= dp_factorial_inverse.at(N - a);
  answer %= M;
  answer *= dp_factorial_inverse.at(a);
  answer %= M;
  return answer;
}
void ll_to_vector(signed base, long long n, vector<signed>& v) {
  long long tempo = n;
  long long tempo2 = n;
  signed n_digit = 1;
  while (tempo2 >= base) {
    tempo2 /= base;
    n_digit++;
  }
  v.assign(n_digit, 0);
  for (signed i = 0; i < n_digit; i++) {
    long long denominator = my_pow(base, n_digit - 1 - i);
    v.at(i) = tempo / denominator;
    tempo -= v.at(i) * denominator;
  }
}
long long char_to_int(char c) {
  switch (c) {
    case '0':
      return 0;
    case '1':
      return 1;
    case '2':
      return 2;
    case '3':
      return 3;
    case '4':
      return 4;
    case '5':
      return 5;
    case '6':
      return 6;
    case '7':
      return 7;
    case '8':
      return 8;
    case '9':
      return 9;
    default:
      return 0;
  }
}
void prime_judge(vector<bool>& prime_or_not) {
  prime_or_not.assign(prime_or_not.size(), true);
  prime_or_not.at(0) = false;
  prime_or_not.at(1) = false;
  long long n = prime_or_not.size() - 1;
  for (long long i = 2; 2 * i <= n; i++) {
    prime_or_not.at(2 * i) = false;
  }
  for (long long i = 3; i * i <= n; i += 2) {
    if (prime_or_not.at(i)) {
      long long j = i * i;
      while (j < n + 1) {
        prime_or_not.at(j) = false;
        j += 2 * i;
      }
    }
  }
};
vector<long long> sieve(long long n) {
  n++;
  vector<long long> res(n, 0);
  for (long long i = 1; i < n; i++) {
    if (i % 2 == 0)
      res.at(i) = 2;
    else
      res.at(i) = i;
  }
  for (long long i = 3; i * i < n; i += 2) {
    if (res.at(i) == i) {
      long long j = i * i;
      while (j < n) {
        if (res.at(j) == j) res.at(j) = i;
        j += 2 * i;
      }
    }
  }
  return res;
};
bool is_prime(long long N) {
  if (N == 1 || N == 0) return false;
  if (N == 2 || N == 3) return true;
  if (N % 2 == 0) return false;
  if (N % 3 == 0) return false;
  for (long long i = 1; (6 * i + 1) * (6 * i + 1) <= N; ++i) {
    if (N % (6 * i + 1) == 0) return false;
  }
  for (long long i = 0; (6 * i + 5) * (6 * i + 5) <= N; ++i) {
    if (N % (6 * i + 5) == 0) return false;
  }
  return true;
}
map<long long, long long> divide_to_prime(long long target) {
  map<long long, long long> res;
  long long upper_lim = ceil(pow((long double)(target), 0.50));
  vector<bool> prime_or_not(upper_lim + 3, true);
  if (upper_lim < 20) prime_or_not.assign(25, true);
  prime_or_not.at(0) = false;
  prime_or_not.at(1) = false;
  prime_judge(prime_or_not);
  long long tempo = target;
  for (long long i = 1; i * i <= target; i++) {
    if (prime_or_not.at(i)) {
      while (tempo % i == 0) {
        tempo /= i;
        res[i]++;
      }
    }
    if (tempo == 1) break;
  }
  if (tempo != 1) res[tempo]++;
  return res;
}
map<long long, long long> divide_to_prime2(long long target,
                                           vector<long long>& min_factor) {
  map<long long, long long> res;
  if (min_factor.empty() || (long long)min_factor.size() - 1 < target)
    min_factor = sieve(target);
  while (target > 1) {
    res[min_factor[target]]++;
    target /= min_factor[target];
  }
  return res;
}
vector<long long> count_dividers(long long target) {
  vector<long long> dividers, tempo;
  long long i = 1;
  while (i * i < target + 1) {
    if (target % i == 0) {
      dividers.push_back(i);
      if (i < target / i) tempo.push_back(target / i);
    }
    i++;
  }
  for (long long j = 0; j < (long long)tempo.size(); j++) {
    dividers.push_back(tempo.at(tempo.size() - 1 - j));
  }
  return dividers;
}
vector<long long> count_dividers2(long long target,
                                  vector<long long>& min_factor) {
  vector<long long> dividers = {1};
  map<long long, long long> memo = divide_to_prime2(target, min_factor);
  for (auto&& iter = memo.begin(); iter != memo.end(); iter++) {
    vector<long long> tempo = dividers;
    for (long long k = 0; k < (long long)tempo.size(); k++) {
      long long times = 1;
      for (long long j = 1; j <= (iter->second); j++) {
        times *= iter->first;
        dividers.push_back(tempo[k] * times);
      }
    }
  }
  sort(dividers.begin(), dividers.end());
  return dividers;
}
void BFS_labyrinth(queue<pair<long long, long long>>& que,
                   vector<vector<long long>>& dist, long long& area) {
  long long H = dist.size();
  long long W = dist.at(0).size();
  while (!que.empty()) {
    long long h, w;
    pair<long long, long long> tempo = que.front();
    que.pop();
    h = tempo.first;
    w = tempo.second;
    for (long long dh = -1; dh <= 1; dh++) {
      for (long long dw = -1; dw <= 1; dw++) {
        if (h + dh < 0 || H <= h + dh) continue;
        if (w + dw < 0 || W <= w + dw) continue;
        if (dh == 0 && dw == 0) continue;
        if (dh * dw != 0) continue;
        if (dist.at(h + dh).at(w + dw) != -1) continue;
        dist.at(h + dh).at(w + dw) = dist.at(h).at(w) + 1;
        que.push(make_pair(h + dh, w + dw));
      }
    }
    if (que.empty()) {
      for (long long i = 0; i < (H); i++) {
        for (long long j = 0; j < (W); j++) {
          if (dist.at(i).at(j) == -1) {
            que.push(make_pair(i, j));
            dist.at(i).at(j) = 0;
            area++;
            break;
          }
        }
        if (!que.empty()) break;
      }
    }
  }
}
void BFS01_labyrinth(deque<pair<long long, long long>>& que,
                     vector<vector<long long>>& dist,
                     vector<vector<long long>>& cost) {
  long long H = dist.size();
  long long W = dist.at(0).size();
  while (!que.empty()) {
    long long h, w;
    pair<long long, long long> tempo = que.front();
    que.pop_front();
    h = tempo.first;
    w = tempo.second;
    for (long long dh = -1; dh <= 1; dh++) {
      for (long long dw = -1; dw <= 1; dw++) {
        if (h + dh < 0 || H <= h + dh) continue;
        if (w + dw < 0 || W <= w + dw) continue;
        if (dh == 0 && dw == 0) continue;
        if (dh * dw != 0) continue;
        if (dist.at(h + dh).at(w + dw) != -1) continue;
        dist.at(h + dh).at(w + dw) =
            dist.at(h).at(w) + cost.at(h + dh).at(w + dw);
        if (cost.at(h + dh).at(w + dw) == 0) {
          que.push_front(make_pair(h + dh, w + dw));
        } else {
          que.push_back(make_pair(h + dh, w + dw));
        }
      }
    }
  }
}
void dfs(const vector<vector<long long>>& G, vector<bool>& seen, long long v) {
  seen.at(v) = true;
  for (long long next_v : G.at(v)) {
    if (seen.at(next_v)) continue;
    dfs(G, seen, next_v);
  }
}
class edge {
 public:
  long long to;
  long long cost;
};
void dijkstra(long long s, const vector<vector<edge>> G,
              vector<long long>& dist) {
  long long V = dist.size();
  dist.assign(V, INF);
  priority_queue<pair<long long, long long>, vector<pair<long long, long long>>,
                 greater<pair<long long, long long>>>
      que;
  dist.at(s) = 0;
  que.push(make_pair(0, s));
  while (!que.empty()) {
    pair<long long, long long> p = que.top();
    que.pop();
    long long v = p.second;
    if (dist.at(v) < p.first) continue;
    for (long long i = 0; i < (long long)G.at(v).size(); i++) {
      edge e = G.at(v).at(i);
      if (dist.at(e.to) > dist.at(v) + e.cost) {
        dist.at(e.to) = dist.at(v) + e.cost;
        que.push(make_pair(dist.at(e.to), e.to));
      }
    }
  }
}
class Edge {
 public:
  long long from;
  long long to;
  long long cost;
};
vector<long long> BellmanFord(const long long s, vector<long long>& dist,
                              vector<Edge> G) {
  const long long V = dist.size();
  vector<long long> res;
  dist.assign(V, INF);
  dist.at(s) = 0;
  for (long long i = 0; i < V; i++) {
    for (long long j = 0; j < (long long)G.size(); j++) {
      Edge e = G.at(j);
      if (dist[e.to] > dist[e.from] + e.cost) {
        dist[e.to] = dist[e.from] + e.cost;
        if (i == V - 1) {
          res.push_back(e.to);
        }
      }
    }
  }
  return res;
}
const long long Vmax2 = 1;
long long dp_warshall[Vmax2][Vmax2];
void warshall_floyd(const long long V, const vector<vector<long long>> G) {
  for (long long i = 0; i < (V); i++) {
    for (long long j = 0; j < (V); j++) {
      dp_warshall[i][j] = G.at(i).at(j);
    }
  }
  for (long long k = 0; k < (V); k++) {
    for (long long i = 0; i < (V); i++) {
      for (long long j = 0; j < (V); j++) {
        dp_warshall[i][j] =
            min(dp_warshall[i][j], dp_warshall[i][k] + dp_warshall[k][j]);
      }
    }
  }
}
class UnionFind {
 public:
  vector<long long> parent;
  vector<long long> rank;
  vector<long long> v_size;
  UnionFind(long long N) : parent(N), rank(N, 0), v_size(N, 1) {
    for (long long i = 0; i < (N); i++) {
      parent[i] = i;
    }
  }
  long long root(long long x) {
    if (parent[x] == x) return x;
    return parent[x] = root(parent[x]);
  }
  void unite(long long x, long long y) {
    long long rx = root(x);
    long long ry = root(y);
    if (rx == ry) return;
    if (rank[rx] < rank[ry]) {
      parent[rx] = ry;
      v_size[ry] += v_size[rx];
    } else {
      parent[ry] = rx;
      v_size[rx] += v_size[ry];
      if (rank[rx] == rank[ry]) rank[rx]++;
    }
  }
  bool same(long long x, long long y) { return (root(x) == root(y)); }
  long long count_tree() {
    long long N = parent.size();
    long long res = 0;
    for (long long i = 0; i < (N); i++) {
      if (root(i) == i) res++;
    }
    return res;
  }
  long long size(long long x) { return v_size[root(x)]; }
};
class wUnionFind {
 public:
  vector<long long> parent;
  vector<long long> diff_weight;
  vector<long long> rank;
  wUnionFind(long long N) : parent(N), diff_weight(N, 0), rank(N, 0) {
    for (long long i = 0; i < (N); i++) {
      parent.at(i) = i;
    }
  }
  long long root(long long x) {
    if (parent.at(x) == x) return x;
    long long r = root(parent.at(x));
    diff_weight.at(x) += diff_weight.at(parent.at(x));
    return parent.at(x) = r;
  }
  long long weight(long long x) {
    root(x);
    return diff_weight.at(x);
  }
  bool unite(long long x, long long y, long long w) {
    long long rx = root(x);
    long long ry = root(y);
    long long diff_weight_to_ry_from_rx = w + weight(x) - weight(y);
    if (rx == ry) return false;
    if (rank.at(rx) < rank.at(ry)) {
      parent.at(rx) = ry;
      diff_weight.at(rx) = -diff_weight_to_ry_from_rx;
    } else {
      parent.at(ry) = rx;
      diff_weight.at(ry) = diff_weight_to_ry_from_rx;
      if (rank.at(rx) == rank.at(ry)) rank.at(rx)++;
    }
    return true;
  }
  bool same(long long x, long long y) { return (root(x) == root(y)); }
  long long count_tree() {
    long long N = parent.size();
    long long res = 0;
    for (long long i = 0; i < (N); i++) {
      if (root(i) == i) res++;
    }
    return res;
  }
};
long double calc_dist(long long x1, long long x2, long long y1, long long y2) {
  long long tempo = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
  long double res = pow((long double)((long double)tempo), 0.50);
  return res;
}
long long doubling(vector<vector<long long>> next, long long v, long long N) {
  vector<signed> memo;
  ll_to_vector(2, N, memo);
  long long M = 0;
  M = memo.size();
  long long now = v;
  for (long long i = 0; i < M; i++) {
    if (N & (long long)(1LL << i)) {
      now = next.at(i).at(now);
    }
  }
  return now;
}
vector<pair<long long, char>> compress(string S) {
  long long N = S.size();
  vector<pair<long long, char>> memo;
  long long tempo = 1;
  for (long long i = 1; i < N; i++) {
    if (i != N - 1) {
      if (S.at(i) == S.at(i - 1))
        tempo++;
      else {
        memo.push_back(make_pair(tempo, S.at(i - 1)));
        tempo = 1;
      }
    } else {
      if (S.at(i) == S.at(i - 1)) {
        tempo++;
        memo.push_back(make_pair(tempo, S.at(i - 1)));
      } else {
        memo.push_back(make_pair(tempo, S.at(i - 1)));
        memo.push_back(make_pair(1, S.at(i)));
      }
    }
  }
  return memo;
}
template <typename T>
class BIT {
 public:
  vector<T> data;
  vector<T> bit;
  long long N;
  BIT(long long n, T ini) : data(n + 1, ini), bit(n + 1, ini), N(n + 1){};
  BIT(long long n) : data(n + 1, 0), bit(n + 1, 0), N(n + 1){};
  void add(long long a, T w) {
    data[a] += w;
    for (long long x = a; x < N; x += x & -x) bit[x] += w;
  }
  T sum(long long a) {
    T res = 0;
    for (long long x = a; x > 0; x -= x & -x) res += bit[x];
    return res;
  }
  T sum(long long l, long long r) {
    if (l == 0 || l == 1)
      return sum(r - 1);
    else
      return sum(r - 1) - sum(l - 1);
  }
  long long lower_bound(T w) {
    if (w <= (T)0) return 0;
    long long x = 0, r = 1;
    while (r * 2 < N) r *= 2;
    for (long long len = r; len > 0; len /= 2) {
      if (x + len < N && bit[x + len] < w) {
        w -= bit[x + len];
        x += len;
      }
    }
    return x + 1;
  }
};
template <typename T>
class BIT_imos {
 public:
  vector<T> data;
  vector<T> data2;
  vector<T> bit;
  vector<T> bit2;
  long long N;
  BIT_imos(long long n, T ini)
      : data(n + 1, ini),
        data2(n + 1, ini),
        bit(n + 1, ini),
        bit2(n + 1, ini),
        N(n + 1){};
  BIT_imos(long long n)
      : data(n + 1, 0),
        data2(n + 1, 0),
        bit(n + 1, 0),
        bit2(n + 1, 0),
        N(n + 1){};
  void add(long long l, long long r, T w) {
    data[l] += w;
    data2[l] += -w * (l - 1);
    if (r < N) {
      data[r] += -w;
      data2[r] += w * (r - 1);
    }
    for (long long x = l; x < N; x += x & -x) bit[x] += w;
    for (long long x = l; x < N; x += x & -x) bit2[x] += -w * (l - 1);
    if (r < N) {
      for (long long x = r; x < N; x += x & -x) bit[x] += -w;
      for (long long x = r; x < N; x += x & -x) bit2[x] += w * (r - 1);
    }
  }
  T sum(long long a) {
    T res = 0;
    for (long long x = a; x > 0; x -= x & -x) res += a * bit[x];
    for (long long x = a; x > 0; x -= x & -x) res += bit2[x];
    return res;
  }
  T sum(long long l, long long r) {
    if (l == 0 || l == 1)
      return sum(r - 1);
    else
      return sum(r - 1) - sum(l - 1);
  }
};
void printf_ld(long double res) { printf("%.12Lf\n", res); }
template <class Cap>
class MaxFlow {
 public:
  MaxFlow() : N(0) {}
  MaxFlow(long long n) : N(n), G(n) {}
  long long add_edge(long long from, long long to, Cap cap) {
    assert(0 <= from && from < N);
    assert(0 <= to && to < N);
    assert(0 <= cap);
    long long m = (long long)(pos.size());
    pos.push_back({from, (long long)(G[from].size())});
    G[from].push_back(edge1{to, (long long)(G[to].size()), cap});
    G[to].push_back(edge1{from, (long long)(G[from].size()) - 1, 0});
    return m;
  }
  struct edge1 {
    long long to;
    long long rev;
    Cap cap;
  };
  struct edge2 {
    long long from;
    long long to;
    Cap cap;
    Cap flow;
  };
  edge2 get_edge(long long i) {
    long long m = (long long)(pos.size());
    assert(0 <= i && i < m);
    auto _e = G[pos[i].first][pos[i].second];
    auto _rev = G[_e.to][_e.rev];
    return edge2{pos[i].first, _e.to, _e.cap + _rev.cap, _rev.cap};
  }
  std::vector<edge2> edges() {
    long long m = (long long)(pos.size());
    std::vector<edge2> res;
    for (long long i = 0; i < m; i++) {
      res.push_back(get_edge(i));
    }
    return res;
  }
  void change_edge(long long i, Cap new_cap, Cap new_flow) {
    long long m = (long long)(pos.size());
    assert(0 <= i && i < m);
    assert(0 <= new_flow && new_flow <= new_cap);
    auto& _e = G[pos[i].first][pos[i].second];
    auto& _rev = G[_e.to][_e.rev];
    _e.cap = new_cap - new_flow;
    _rev.cap = new_flow;
  }
  std::vector<bool> min_cut(long long s) {
    std::vector<bool> seen(N);
    queue<long long> que;
    que.push(s);
    while (!que.empty()) {
      long long v = que.front();
      que.pop();
      seen[v] = true;
      for (auto e : G[v]) {
        if (e.cap && !seen[e.to]) {
          seen[e.to] = true;
          que.push(e.to);
        }
      }
    }
    return seen;
  }
  Cap dfs(long long v, const long long t, Cap flow, vector<bool>& seen) {
    if (v == t) return flow;
    seen[v] = true;
    for (long long i = 0; i < (long long)(G[v].size()); i++) {
      edge1& e = G[v][i];
      if (seen[e.to] || e.cap <= 0) continue;
      long long res = dfs(e.to, t, min(flow, e.cap), seen);
      if (res > 0) {
        e.cap -= res;
        G[e.to][e.rev].cap += res;
        return res;
      }
    }
    return 0;
  };
  Cap flow(long long s, long long t) {
    assert(0 <= s && s < N);
    assert(0 <= t && t < N);
    Cap res = 0;
    while (true) {
      vector<bool> seen(N, false);
      Cap flow = dfs(s, t, inf, seen);
      if (flow == 0) return res;
      res += flow;
    }
  }

 private:
  long long N;
  std::vector<std::pair<long long, long long>> pos;
  std::vector<std::vector<edge1>> G;
  const Cap inf = std::numeric_limits<Cap>::max() - 3;
};
class SegmentTree_RAQ_and_RSQ2 {
 public:
  long long ini = 0;
  long long ini_lazy = 0;
  long long Size;
  vector<long long> node;
  vector<long long> lazy;
  SegmentTree_RAQ_and_RSQ2(long long N) : Size(N), node(N) { initialize(N); }
  SegmentTree_RAQ_and_RSQ2(long long N, long long ini)
      : ini(ini), Size(N), node(N) {
    initialize(N);
  }
  SegmentTree_RAQ_and_RSQ2(vector<long long> v)
      : Size(v.size()), node(v.size()) {
    initialize(v);
  }
  SegmentTree_RAQ_and_RSQ2(vector<long long> v, long long ini)
      : ini(ini), Size(v.size()), node(v.size()) {
    initialize(v);
  }
  void initialize(long long N) {
    long long new_N = 1;
    while (new_N < N) new_N *= 2;
    Size = new_N;
    node.assign(2 * Size - 1, ini);
    lazy.assign(2 * Size - 1, ini_lazy);
  }
  void initialize(vector<long long> v) {
    long long new_N = 1;
    while (new_N < (long long)v.size()) new_N *= 2;
    Size = new_N;
    node.assign(2 * Size - 1, ini);
    lazy.assign(2 * Size - 1, ini_lazy);
    for (long long i = 0; i < (long long)v.size(); i++)
      node.at(Size - 1 + i) = v.at(i);
    for (long long i = Size - 2; i >= 0; i--) {
      node.at(i) = node.at(2 * i + 1) + node.at(2 * i + 2);
      node.at(i) %= MOD;
    }
  }
  void eval(long long k) {
    if (lazy.at(k) == ini_lazy) return;
    if (k < Size - 1) {
      long long tempo = lazy.at(k) * 499122177;
      tempo %= MOD;
      lazy.at(k * 2 + 1) += tempo;
      lazy.at(k * 2 + 2) += tempo;
      lazy.at(k * 2 + 1) %= MOD;
      lazy.at(k * 2 + 2) %= MOD;
    }
    node.at(k) += lazy.at(k);
    node.at(k) %= MOD;
    lazy.at(k) = ini_lazy;
  }
  void add_sub(long long a, long long b, long long x, long long k, long long l,
               long long r) {
    eval(k);
    if (r <= a || b <= l) return;
    if (a <= l && r <= b) {
      lazy.at(k) = x * (r - l);
      eval(k);
    } else {
      add_sub(a, b, x, k * 2 + 1, l, (l + r) / 2);
      add_sub(a, b, x, k * 2 + 2, (l + r) / 2, r);
      node.at(k) = node.at(k * 2 + 1) + node.at(k * 2 + 2);
      node.at(k) %= MOD;
    }
  }
  void add(long long a, long long b, long long x) {
    add_sub(a, b, x, 0, 0, Size);
  }
  long long query_sub(long long a, long long b, long long k, long long l,
                      long long r) {
    eval(k);
    if (r <= a || b <= l) return ini;
    if (a <= l && r <= b)
      return node.at(k) % MOD;
    else {
      long long vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
      long long vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
      long long res = vl + vr;
      res %= MOD;
      return res;
    }
  }
  long long query(long long a, long long b) {
    return query_sub(a, b, 0, 0, Size);
  }
  void node_show() {
    cout << endl;
    for (long long i = 0; i < Size - 1; i++) {
      eval(i);
      cout << node[i] << endl;
    }
    cout << endl;
    for (long long i = Size - 1; i < 2 * Size - 1; i++) {
      eval(i);
      cout << node[i] << endl;
    }
  }
};
signed main() {
  long long N, K;
  cin >> N >> K;
  vector<long long> L(K), R(K);
  for (long long i = 0; i < (K); i++) {
    cin >> L.at(i) >> R.at(i);
  }
  SegmentTree_RAQ_and_RSQ2 tree(N);
  tree.add(0, 1, 1);
  for (long long i = 0; i <= N - 1; i++) {
    for (long long j = 0; j < (K); j++) {
      long long l = i + L.at(j);
      long long r = i + R.at(j) + 1;
      if (r > N) r = N;
      if (l >= N) continue;
      long long w = tree.query(i, i + 1);
      tree.add(l, r, w);
    }
  }
  long long res = tree.query(N - 1, N);
  res %= MOD;
  if (res < 0) res += MOD;
  cout << res << endl;
}
