【模板】多项式半家桶 version 2

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
typedef long long LL;
template <unsigned umod>
struct modint {
  static constexpr int mod = umod;
  unsigned v;
  modint() : v(0) {}
  template <class T>
    modint(T x) {
      x %= mod;
      if (x < 0) x += mod;
      v = x;
    }
  modint operator+() const { return *this; }
  modint operator-() const { return modint() - *this; }
  friend int raw(const modint &self) { return self.v; }
  friend istream& operator>>(istream& is, modint& self) {
    string str;
    is >> str;
    self = 0;
    int flag = 1;
    for (char ch : str) {
      if (ch == '-') flag = -1;
      else assert(isdigit(ch)), self = self * 10 + ch - '0';
    }
    self *= flag;
    return is;
  }
  friend ostream& operator<<(ostream& os, const modint& self) { return os << raw(self); }
  modint &operator+=(const modint &rhs) {
    v += rhs.v;
    if (v >= umod) v -= umod;
    return *this;
  }
  modint &operator-=(const modint &rhs) {
    v -= rhs.v;
    if (v >= umod) v += umod;
    return *this;
  }
  modint &operator*=(const modint &rhs) {
    v = static_cast<unsigned>(1ull * v * rhs.v % umod);
    return *this;
  }
  modint &operator/=(const modint &rhs) {
    assert(rhs.v);
    return *this *= qpow(rhs, mod - 2);
  }
  template <class T>
    friend modint qpow(modint a, T b) {
      modint r = 1;
      for (; b; b >>= 1, a *= a)
        if (b & 1) r *= a;
      return r;
    }
  friend modint operator+(modint lhs, const modint &rhs) { return lhs += rhs; }
  friend modint operator-(modint lhs, const modint &rhs) { return lhs -= rhs; }
  friend modint operator*(modint lhs, const modint &rhs) { return lhs *= rhs; }
  friend modint operator/(modint lhs, const modint &rhs) { return lhs /= rhs; }
  friend bool operator==(const modint &lhs, const modint &rhs) {
    return lhs.v == rhs.v;
  }
  friend bool operator!=(const modint &lhs, const modint &rhs) {
    return lhs.v != rhs.v;
  }
};
typedef modint<998244353> mint;
struct poly : vector<mint> {
  static int glim(const int &x) { return 1 << (32 - __builtin_clz(x)); }
  static int bitctz(const int &x) { return __builtin_ctz(x); }
  poly() {}
  explicit poly(int n) : vector<mint>(n) {}
  poly(const vector<mint>& vec) : vector<mint>(vec) {}
  poly(initializer_list<mint> il) : vector<mint>(il) {}
  mint operator()(const mint &x) const;
  void ntt(const int &op);
  poly getInv(int len) const;
};
void print(const poly a) {
  for (int i = 0; i < a.size(); i++) debug("%d, ", raw(a[i]));
  debug("\n");
}
mint poly::operator()(const mint &x) const {
  const vector<mint>& a = *this;
  mint res = 0;
  for (int i = (int)a.size() - 1; i >= 0; i--) {
    res = res * x + a[i];
  }
  return res;
}
void poly::ntt(const int &op) {
  static bool wns_flag = false;
  static vector<mint> wns;
  if (!wns_flag) {
    wns_flag = true;
    for (int j = 1; j <= 23; j++) {
      wns.push_back(qpow(mint(3), raw(mint(-1)) >> j));
    }
  }
  vector<mint>& a = *this;
  int n = a.size();
  for (int i = 1, r = 0; i < n; i++) {
    r ^= n - (1 << (bitctz(n) - bitctz(i) - 1));
    if (i < r) std::swap(a[i], a[r]);
  }
  vector<mint> w(n);
  for (int k = 1, len = 2; len <= n; k <<= 1, len <<= 1) {
    mint wn = wns[bitctz(k)];
    for (int i = raw(w[0] = 1); i < k; i++) w[i] = w[i - 1] * wn;
    for (int i = 0; i < n; i += len) {
      for (int j = 0; j < k; j++) {
        mint x = a[i + j], y = a[i + j + k] * w[j];
        a[i + j] = x + y, a[i + j + k] = x - y;
      }
    }
  }
  if (op == -1) {
    mint iz = mint(1) / n;
    for (int i = 0; i < n; i++) a[i] *= iz;
    reverse(a.begin() + 1, a.end());
  }
}
void ntt(poly &a, const int &op) { return a.ntt(op); }
poly poly::getInv(int lim) const {
  const vector<mint>& a = *this;
  poly b{1 / a[0]};
  for (int len = 2; len <= glim(lim); len <<= 1) {
    poly c = vector<mint>(a.begin(), a.begin() + min(len, (int)a.size()));
    b.resize(len << 1), b.ntt(1);
    c.resize(len << 1), c.ntt(1);
    for (int i = 0; i < len << 1; i++) {
      b[i] *= 2 - b[i] * c[i];
    }
    b.ntt(-1), b.resize(len);
  }
  b.resize(lim);
  return b;
}
poly getInv(const poly& a, int lim) { return a.getInv(lim); }
poly operator+=(poly& a, const poly& b) {
  if (a.size() < b.size()) a.resize(b.size());
  for (int i = 0; i < b.size(); i++) a[i] += b[i];
  return a;
}
poly operator-=(poly& a, const poly& b) {
  if (a.size() < b.size()) a.resize(b.size());
  for (int i = 0; i < b.size(); i++) a[i] -= b[i];
  return a;
}
poly operator*=(poly& a, const mint& k) {
  for (int i = 0; i < a.size(); i++) a[i] *= k;
  return a;
}
poly operator<<=(poly& a, const int& k) {
  // mnltiple by x^k
  a.insert(a.begin(), k, 0);
  return a;
}
poly operator>>=(poly& a, const int& k) {
  // divide by x^k
  a.erase(a.begin(), a.begin() + min(k, (int)a.size()));
  return a;
}
poly operator*=(poly& a, poly b) {
  if (a.empty() || b.empty()) return {};
  int rlen = a.size() + b.size() - 1;
  int len = poly::glim(rlen);
  if (1ll * a.size() * b.size() <= len * poly::bitctz(len)) {
    a.resize(rlen);
    for (int i = rlen - b.size(); i >= 0; i--) {
      for (int j = 1; j < b.size(); j++) a[i + j] += a[i] * b[j];
      a[i] *= b[0];
    }
  } else {
    a.resize(len), a.ntt(1);
    b.resize(len), b.ntt(1);
    for (int i = 0; i < len; i++) a[i] *= b[i];
    a.ntt(-1), a.resize(rlen);
  }
  return a;
}
poly operator+(poly a, const poly& b) { return a += b; }
poly operator-(poly a, const poly& b) { return a -= b; }
poly operator*(poly a, const mint& k) { return a *= k; }
poly operator*(const mint& k, poly a) { return a *= k; }
poly operator<<(poly a, const int& k) { return a <<= k; }
poly operator>>(poly a, const int& k) { return a >>= k; }
poly operator*(poly a, const poly& b) { return a *= b; }
template <class T>
mint divide_at(poly f, poly g, T n) {
  for (; n; n >>= 1) {
    poly r = g;
    for (int i = 1; i < r.size(); i += 2) r[i] *= -1;
    f *= r;
    g *= r;
    for (int i = n & 1; i < f.size(); i += 2) f[i >> 1] = f[i];
    f.resize((f.size() + 1) >> 1);
    for (int i = 0; i < g.size(); i += 2) g[i >> 1] = g[i];
    g.resize((g.size() + 1) >> 1);
  }
  return f.empty() ? 0 : f[0] / g[0];
}
template <class T>
mint linear_rec(poly a, poly f, T n) {
  // a[n] = sum_i f[i] * a[n - i]
  a.resize(f.size() - 1);
  f = poly{1} - f;
  poly g = a * f;
  g.resize(a.size());
  return divide_at(g, f, n);
}
poly BM(poly a) {
  poly ans, lst;
  int w = 0;
  mint delta = 0;
  for (int i = 0; i < a.size(); i++) {
    mint tmp = -a[i];
    for (int j = 0; j < ans.size(); j++) tmp += ans[j] * a[i - j - 1];
    if (tmp == 0) continue;
    if (ans.empty()) {
      w = i;
      delta = tmp;
      ans = vector<mint>(i + 1, 0);
    } else {
      auto now = ans;
      mint mul = -tmp / delta;
      if (ans.size() < lst.size() + i - w) ans.resize(lst.size() + i - w);
      ans[i - w - 1] -= mul;
      for (int j = 0; j < lst.size(); j++) ans[i - w + j] += lst[j] * mul;
      if (now.size() <= lst.size() + i - w) {
        w = i;
        lst = now;
        delta = tmp;
      }
    }
  }
  return ans << 1;
}
poly lagrange(const vector<pair<mint, mint>> &a) {
  poly ans(a.size()), product{1};
  for (int i = 0; i < a.size(); i++) {
    product *= poly{-a[i].first, 1};
  }
  auto divide2 = [&](poly a, mint b) {
    poly res(a.size() - 1);
    for (int i = (int)a.size() - 1; i >= 1; i--) {
      res[i - 1] = a[i];
      a[i - 1] -= a[i] * b;
    }
    return res;
  };
  for (int i = 0; i < a.size(); i++) {
    mint denos = 1;
    for (int j = 0; j < a.size(); j++) {
      if (i != j) denos *= a[i].first - a[j].first;
    }
    poly numes = divide2(product, -a[i].first);
    ans += a[i].second / denos * numes;
  }
  return ans;
}
int main() {
#ifndef LOCAL
  cin.tie(nullptr)->sync_with_stdio(false);
#endif  
  int n, k;
  cin >> n >> k;
  vector<pair<mint, mint>> a(n);
  for (auto& elem : a) cin >> elem.first >> elem.second;
  cout << lagrange(a)(k) << endl;
  return 0;
}