#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template <class T>
using PQ = priority_queue<T>;
template <class T>
using PQG = priority_queue<T, vector<T>, greater<T>>;
const int INF = 0xccccccc;
const ll LINF = 0xcccccccccccccccLL;
template <typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {
  return a < b && (a = b, true);
}
template <typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {
  return a > b && (a = b, true);
}
template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
  return is >> p.first >> p.second;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
  return os << p.first << ' ' << p.second;
}
const unsigned int mod = 998244353;
struct mint {
  unsigned int x;
  mint() : x(0) {}
  mint(int64_t x_) {
    int64_t v = int64_t(x_ % mod);
    if (v < 0) v += mod;
    x = (unsigned int)v;
  }
  static mint row(int v) {
    mint v_;
    v_.x = v;
    return v_;
  }
  mint operator-() const { return mint(-int64_t(x)); }
  mint &operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint &operator-=(const mint a) {
    if ((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint &operator*=(const mint a) {
    uint64_t z = x;
    z *= a.x;
    x = (unsigned int)(z % mod);
    return *this;
  }
  mint operator+(const mint a) const { return mint(*this) += a; }
  mint operator-(const mint a) const { return mint(*this) -= a; }
  mint operator*(const mint a) const { return mint(*this) *= a; }
  friend bool operator==(const mint &a, const mint &b) { return a.x == b.x; }
  friend bool operator!=(const mint &a, const mint &b) { return a.x != b.x; }
  mint &operator++() {
    x++;
    if (x == mod) x = 0;
    return *this;
  }
  mint &operator--() {
    if (x == 0) x = mod;
    x--;
    return *this;
  }
  mint operator++(int) {
    mint result = *this;
    ++*this;
    return result;
  }
  mint operator--(int) {
    mint result = *this;
    --*this;
    return result;
  }
  mint pow(int64_t t) const {
    mint x_ = *this, r = 1;
    while (t) {
      if (t & 1) r *= x_;
      x_ *= x_;
      t >>= 1;
    }
    return r;
  }
  mint inv() const { return pow(mod - 2); }
  mint &operator/=(const mint a) { return *this *= a.inv(); }
  mint operator/(const mint a) { return mint(*this) /= a; }
};
struct combination {
  vector<mint> frac, ifrac;
  combination(int n) : frac(n + 1), ifrac(n + 1) {
    assert((unsigned int)(n) < mod);
    frac[0] = 1;
    for (int i = 1; i <= n; ++i) frac[i] = frac[i - 1] * i;
    ifrac[n] = frac[n].inv();
    for (int i = n; i >= 1; --i) ifrac[i - 1] = ifrac[i] * i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return frac[n] * ifrac[k] * ifrac[n - k];
  }
} c(1000000);
istream &operator>>(istream &is, mint &a) { return is >> a.x; }
ostream &operator<<(ostream &os, const mint &a) { return os << a.x; }
string to_string(mint a) { return to_string(a.x); }
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string(string(s)); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(vector<bool> v) {
  string res = "{";
  for (int i = 0; i < int(v.size()); i++) {
    if (i) res += ", ";
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res;
  for (size_t i = 0; i < N; i++) res += char('0' + v[i]);
  return res;
}
template <class A, class B>
string to_string(pair<A, B>);
template <class A, class B, class C>
string to_string(tuple<A, B, C>);
template <class A, class B, class C, class D>
string to_string(tuple<A, B, C, D>);
template <class A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <class A, class B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <class A, class B, class C>
string to_string(tuple<A, B, C> t) {
  return "(" + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " +
         to_string(get<2>(t)) + ")";
}
template <class A, class B, class C, class D>
string to_string(tuple<A, B, C, D> t) {
  return "(" + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " +
         to_string(get<2>(t)) + ", " + to_string(get<3>(t)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << ' ' << to_string(H);
  debug_out(T...);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<tuple<int, int, int>> lr(n);
  for (int i = 0; i < n; ++i) {
    int l, r;
    cin >> l >> r;
    lr[i] = {l, r, i};
  }
  vvi G(n);
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    G[a].emplace_back(b);
    G[b].emplace_back(a);
  }
  sort(lr.begin(), lr.end());
  PQG<P> q;
  set<P> lst;
  set<int> ids;
  int j = 0;
  mint ans;
  vvi counter(21, vi(41));
  counter[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    bool ch = false;
    while (j < n and get<0>(lr[j]) == i) {
      auto [l, r, id] = lr[j];
      for (int ne : G[id]) {
        if (ids.find(ne) != ids.end()) lst.emplace(id, ne), ch = true;
      }
      ids.emplace(id);
      q.emplace(r, id);
      j++;
    }
    while (!q.empty() and q.top().first == i - 1) {
      int u = q.top().second;
      q.pop();
      vector<P> ers;
      for (auto p : lst) {
        if (p.first == u or p.second == u) {
          ers.emplace_back(p);
          ch = true;
        }
      }
      for (auto p : ers) lst.erase(lst.find(p));
      ids.erase(ids.find(u));
    }
    if (ch) {
      for (int i = 0; i < 21; ++i)
        fill(counter[i].begin(), counter[i].begin() + i * 2 + 1, 0);
      int num = lst.size();
      for (int siz = 0; siz < num + 1; ++siz) {
        int j = (1 << siz) - 1;
        while (j < 1 << num) {
          vi iid;
          iid.reserve(siz * 2);
          int cnt = 0;
          for (auto p : lst) {
            if (j >> cnt++ & 1) {
              iid.push_back(p.first);
              iid.push_back(p.second);
            }
          }
          sort(iid.begin(), iid.end());
          auto itr = unique(iid.begin(), iid.end());
          counter[siz][itr - iid.begin()]++;
          if (!j) break;
          int x = j & -j, y = x + j, z = j & ~y;
          j = (z / (x << 1)) + y;
        }
      }
    }
    for (int j = 0; j < 21; ++j) {
      for (int k = 0; k < j * 2 + 1; ++k) {
        if (j & 1)
          ans -= c(int(ids.size()) - k, i - k) * counter[j][k];
        else
          ans += c(int(ids.size()) - k, i - k) * counter[j][k];
      }
    }
  }
  cout << ans << endl;
}

### Prompt

Please create a solution in Cpp to the following problem:

Polycarp plays a (yet another!) strategic computer game. In this game, he leads an army of mercenaries.

Polycarp wants to gather his army for a quest. There are n mercenaries for hire, and the army should consist of some subset of them.

The i-th mercenary can be chosen if the resulting number of chosen mercenaries is not less than l_i (otherwise he deems the quest to be doomed) and not greater than r_i (he doesn't want to share the trophies with too many other mercenaries). Furthermore, m pairs of mercenaries hate each other and cannot be chosen for the same quest. 

How many non-empty subsets does Polycarp need to consider? In other words, calculate the number of non-empty subsets of mercenaries such that the size of this subset belongs to [l_i, r_i] for each chosen mercenary, and there are no two mercenaries in the subset that hate each other.

The answer may be large, so calculate it modulo 998244353.

Input

The first line contains two integers n and m (1 ≤ n ≤ 3 ⋅ 10^5, 0 ≤ m ≤ min(20, (n(n-1))/(2))) — the number of mercenaries and the number of pairs of mercenaries that hate each other.

Then n lines follow, the i-th of them contains two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ n).

Then m lines follow, the i-th of them contains two integers a_i and b_i (1 ≤ a_i < b_i ≤ n) denoting that the mercenaries a_i and b_i hate each other. There are no two equal pairs in this list.

Output

Print one integer — the number of non-empty subsets meeting the constraints, taken modulo 998244353.

Examples

Input


3 0
1 1
2 3
1 3


Output


3


Input


3 1
1 1
2 3
1 3
2 3


Output


2

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template <class T>
using PQ = priority_queue<T>;
template <class T>
using PQG = priority_queue<T, vector<T>, greater<T>>;
const int INF = 0xccccccc;
const ll LINF = 0xcccccccccccccccLL;
template <typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {
  return a < b && (a = b, true);
}
template <typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {
  return a > b && (a = b, true);
}
template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
  return is >> p.first >> p.second;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
  return os << p.first << ' ' << p.second;
}
const unsigned int mod = 998244353;
struct mint {
  unsigned int x;
  mint() : x(0) {}
  mint(int64_t x_) {
    int64_t v = int64_t(x_ % mod);
    if (v < 0) v += mod;
    x = (unsigned int)v;
  }
  static mint row(int v) {
    mint v_;
    v_.x = v;
    return v_;
  }
  mint operator-() const { return mint(-int64_t(x)); }
  mint &operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint &operator-=(const mint a) {
    if ((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint &operator*=(const mint a) {
    uint64_t z = x;
    z *= a.x;
    x = (unsigned int)(z % mod);
    return *this;
  }
  mint operator+(const mint a) const { return mint(*this) += a; }
  mint operator-(const mint a) const { return mint(*this) -= a; }
  mint operator*(const mint a) const { return mint(*this) *= a; }
  friend bool operator==(const mint &a, const mint &b) { return a.x == b.x; }
  friend bool operator!=(const mint &a, const mint &b) { return a.x != b.x; }
  mint &operator++() {
    x++;
    if (x == mod) x = 0;
    return *this;
  }
  mint &operator--() {
    if (x == 0) x = mod;
    x--;
    return *this;
  }
  mint operator++(int) {
    mint result = *this;
    ++*this;
    return result;
  }
  mint operator--(int) {
    mint result = *this;
    --*this;
    return result;
  }
  mint pow(int64_t t) const {
    mint x_ = *this, r = 1;
    while (t) {
      if (t & 1) r *= x_;
      x_ *= x_;
      t >>= 1;
    }
    return r;
  }
  mint inv() const { return pow(mod - 2); }
  mint &operator/=(const mint a) { return *this *= a.inv(); }
  mint operator/(const mint a) { return mint(*this) /= a; }
};
struct combination {
  vector<mint> frac, ifrac;
  combination(int n) : frac(n + 1), ifrac(n + 1) {
    assert((unsigned int)(n) < mod);
    frac[0] = 1;
    for (int i = 1; i <= n; ++i) frac[i] = frac[i - 1] * i;
    ifrac[n] = frac[n].inv();
    for (int i = n; i >= 1; --i) ifrac[i - 1] = ifrac[i] * i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return frac[n] * ifrac[k] * ifrac[n - k];
  }
} c(1000000);
istream &operator>>(istream &is, mint &a) { return is >> a.x; }
ostream &operator<<(ostream &os, const mint &a) { return os << a.x; }
string to_string(mint a) { return to_string(a.x); }
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string(string(s)); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(vector<bool> v) {
  string res = "{";
  for (int i = 0; i < int(v.size()); i++) {
    if (i) res += ", ";
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res;
  for (size_t i = 0; i < N; i++) res += char('0' + v[i]);
  return res;
}
template <class A, class B>
string to_string(pair<A, B>);
template <class A, class B, class C>
string to_string(tuple<A, B, C>);
template <class A, class B, class C, class D>
string to_string(tuple<A, B, C, D>);
template <class A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <class A, class B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <class A, class B, class C>
string to_string(tuple<A, B, C> t) {
  return "(" + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " +
         to_string(get<2>(t)) + ")";
}
template <class A, class B, class C, class D>
string to_string(tuple<A, B, C, D> t) {
  return "(" + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " +
         to_string(get<2>(t)) + ", " + to_string(get<3>(t)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << ' ' << to_string(H);
  debug_out(T...);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<tuple<int, int, int>> lr(n);
  for (int i = 0; i < n; ++i) {
    int l, r;
    cin >> l >> r;
    lr[i] = {l, r, i};
  }
  vvi G(n);
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    G[a].emplace_back(b);
    G[b].emplace_back(a);
  }
  sort(lr.begin(), lr.end());
  PQG<P> q;
  set<P> lst;
  set<int> ids;
  int j = 0;
  mint ans;
  vvi counter(21, vi(41));
  counter[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    bool ch = false;
    while (j < n and get<0>(lr[j]) == i) {
      auto [l, r, id] = lr[j];
      for (int ne : G[id]) {
        if (ids.find(ne) != ids.end()) lst.emplace(id, ne), ch = true;
      }
      ids.emplace(id);
      q.emplace(r, id);
      j++;
    }
    while (!q.empty() and q.top().first == i - 1) {
      int u = q.top().second;
      q.pop();
      vector<P> ers;
      for (auto p : lst) {
        if (p.first == u or p.second == u) {
          ers.emplace_back(p);
          ch = true;
        }
      }
      for (auto p : ers) lst.erase(lst.find(p));
      ids.erase(ids.find(u));
    }
    if (ch) {
      for (int i = 0; i < 21; ++i)
        fill(counter[i].begin(), counter[i].begin() + i * 2 + 1, 0);
      int num = lst.size();
      for (int siz = 0; siz < num + 1; ++siz) {
        int j = (1 << siz) - 1;
        while (j < 1 << num) {
          vi iid;
          iid.reserve(siz * 2);
          int cnt = 0;
          for (auto p : lst) {
            if (j >> cnt++ & 1) {
              iid.push_back(p.first);
              iid.push_back(p.second);
            }
          }
          sort(iid.begin(), iid.end());
          auto itr = unique(iid.begin(), iid.end());
          counter[siz][itr - iid.begin()]++;
          if (!j) break;
          int x = j & -j, y = x + j, z = j & ~y;
          j = (z / (x << 1)) + y;
        }
      }
    }
    for (int j = 0; j < 21; ++j) {
      for (int k = 0; k < j * 2 + 1; ++k) {
        if (j & 1)
          ans -= c(int(ids.size()) - k, i - k) * counter[j][k];
        else
          ans += c(int(ids.size()) - k, i - k) * counter[j][k];
      }
    }
  }
  cout << ans << endl;
}

```