Language: C++

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll md = 998244353;

template <typename T>
class LazySegmentTree {
  vector<T> data_;
  vector<T> lazy_;
  int size_;

  void Eval(int k) {
    if (lazy_[k] == 0) {
      return;
    }

    if (k < size_ - 1) {
      lazy_[k * 2 + 1] += lazy_[k];
      lazy_[k * 2 + 2] += lazy_[k];
    }

    data_[k] += lazy_[k];
    lazy_[k] = 0;
  }

  void UpdateSub(int a, int b, T x, int k, int l, int r) {
    Eval(k);
    if (a <= l && r <= b) {
      lazy_[k] += x;
      Eval(k);
    } else if (a < r && l < b) {
      UpdateSub(a, b, x, k * 2 + 1, l, (l + r) / 2);
      UpdateSub(a, b, x, k * 2 + 2, (l + r) / 2, r);
      data_[k] = data_[k * 2 + 1] + data_[k * 2 + 2];
    }
  }

  T QuerySub(int a, int b, int k, int l, int r) {
    Eval(k);
    if (r <= a || b <= l) {
      return 0;
    } else if (a <= l && r <= b) {
      return data_[k];
    } else {
      return QuerySub(a, b, k * 2 + 1, l, (l + r) / 2) +
             QuerySub(a, b, k * 2 + 2, (l + r) / 2, r);
    }
  }

 public:
  LazySegmentTree(int size) : data_(), lazy_() {
    int n = 1;
    while (size > n) {
      n *= 2;
    }

    size_ = n;
    data_.resize(n * 2 - 1);
    lazy_.resize(n * 2 - 1);
    fill(data_.begin(), data_.end(), 0);
    fill(lazy_.begin(), lazy_.end(), 0);
  }

  void Update(int a, int b, T x) { UpdateSub(a, b, x, 0, 0, size_); }
  T Query(int a, int b) { return QuerySub(a, b, 0, 0, size_); }
  T Query(int a) { return Query(a, a + 1); }
};

namespace mod {

template <class T, int M>
class MInt;

template <class T, int M>
MInt<T, M> Pow(const MInt<T, M> &base, T exp);

template <class T, int M>
MInt<T, M> Inv(const MInt<T, M> &n);

template <class T, int M>
class MInt {
  T n_;

 public:
  MInt() : n_(0) {}
  MInt(T n) : n_((n % M + M) % M) {}

  MInt &operator+=(const MInt &rhs) {
    n_ += rhs.n_;
    if (n_ >= M) {
      n_ -= M;
    }

    return *this;
  }

  MInt &operator-=(const MInt &rhs) {
    n_ += M - rhs.n_;
    if (n_ >= M) {
      n_ -= M;
    }

    return *this;
  }

  MInt &operator*=(const MInt &rhs) {
    n_ = n_ * rhs.n_ % M;
    return *this;
  }

  MInt &operator/=(const MInt &rhs) { return (*this) *= Inv(rhs); }

  T Get() { return n_; }
};

template <class T, int M>
MInt<T, M> operator-(const MInt<T, M> &lhs, const MInt<T, M> &rhs) {
  MInt<T, M> res(lhs);
  return res -= rhs;
}

template <class T, int M>
MInt<T, M> operator+(const MInt<T, M> &lhs, const MInt<T, M> &rhs) {
  MInt<T, M> res(lhs);
  return res += rhs;
}

template <class T, int M>
MInt<T, M> operator*(const MInt<T, M> &lhs, const MInt<T, M> &rhs) {
  MInt<T, M> res(lhs);
  return res *= rhs;
}

template <class T, int M>
MInt<T, M> operator/(const MInt<T, M> &lhs, const MInt<T, M> &rhs) {
  MInt<T, M> res(lhs);
  return res /= rhs;
}

template <class T, int M>
MInt<T, M> Pow(const MInt<T, M> &base, T exp) {
  if (exp == 0) {
    return 1;
  }

  auto a = Pow(base, exp / 2);
  a *= a;
  if (exp % 2 == 1) {
    a *= base;
  }

  return a;
}

template <class T, int M>
MInt<T, M> Inv(const MInt<T, M> &n) {
  return Pow(n, static_cast<T>(M - 2));
}
}  // namespace mod

using MInt = mod::MInt<long long, md>;

int main(int argc, const char *argv[]) {
  int n, k;
  cin >> n >> k;

  vector<pair<int, int>> vp(k);
  for (auto &p : vp) {
    cin >> p.first >> p.second;
  }

  LazySegmentTree<MInt> seg_tree(n * 2 + 1);
  seg_tree.Update(0, 1, 1);
  for (int i = 0; i < n; ++i) {
    auto x = seg_tree.Query(i);
    for (auto &p : vp) {
      seg_tree.Update(i + p.first, p.second + 1, x);
    }
  }

  cout << seg_tree.Query(n).Get() << '\n';
  return 0;
}

Compiler output:
a.cc: In instantiation of 'void LazySegmentTree<T>::Eval(int) [with T = mod::MInt<long long int, 998244353>]':
a.cc:29:5:   required from 'void LazySegmentTree<T>::UpdateSub(int, int, T, int, int, int) [with T = mod::MInt<long long int, 998244353>]'
   29 |     Eval(k);
      |     ^~~~
a.cc:66:36:   required from 'void LazySegmentTree<T>::Update(int, int, T) [with T = mod::MInt<long long int, 998244353>]'
   66 |   void Update(int a, int b, T x) { UpdateSub(a, b, x, 0, 0, size_); }
      |                                    ^~~~~~~~~
a.cc:175:18:   required from here
  175 |   seg_tree.Update(0, 1, 1);
      |   ~~~~~~~~~~~~~~~^~~~~~~~~
a.cc:15:18: error: no match for 'operator==' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<mod::MInt<long long int, 998244353> >, mod::MInt<long long int, 998244353> >::value_type' {aka 'mod::MInt<long long int, 998244353>'} and 'int')
   15 |     if (lazy_[k] == 0) {
      |         ~~~~~~~~~^~~~
In file included from /usr/include/c++/14/regex:68,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:181,
                 from a.cc:1:
/usr/include/c++/14/bits/regex.h:1103:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator==(const sub_match<_BiIter>&, const sub_match<_BiIter>&)'
 1103 |     operator==(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1103:5: note:   template argument deduction/substitution failed:
a.cc:15:18: note:   '__gnu_cxx::__alloc_traits<std::allocator<mod::MInt<long long int, 998244353> >, mod::MInt<long long int, 998244353> >::value_type' {aka 'mod::MInt<long long int, 998244353>'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   15 |     if (lazy_[k] == 0) {
      |         ~~~~~~~~~^~~~
/usr/include/c++/14/bits/regex.h:1199:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator==(__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const sub_match<_BiIter>&)'
 1199 |     operator==(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1199:5: note:   template argument deduction/substitution failed:
a.cc:15:18: note:   '__gnu_cxx::__alloc_traits<std::allocator<mod::MInt<long long int, 998244353> >, mod::MInt<long long int, 998244353> >::value_type' {aka 'mod::MInt<long long int, 998244353>'} is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
   15 |     if (lazy_[k] == 0) {
      |         ~~~~~~~~~^~~~
/usr/include/c++/14/bits/regex.h:1274:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator==(const sub_match<_BiIter>&, __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)'
 1274 |     operator==(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1274:5: note:   template argument deduction/substitution failed:
a.cc:15:18: note:   '__gnu_cxx::__alloc_traits<std::allocator<mod::MInt<long long int, 998244353> >, mod::MInt<long long int, 998244353> >::value_type' {aka 'mod::MInt<long long int, 998244353>'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   15 |     if (lazy_[k] == 0) {
      |         ~~~~~~~~~^~~~
/usr/include/c++/14/bits/regex.h:1366:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator==(const typename std::iterator_traits<_Iter>::value_type*, const sub_match<_BiIter>&)'
 1366 |     operator==(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1366:5: note:   template argument deduction/substitution failed:
a.cc:15:18: note:   mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'int'
   15 |     if (lazy_[k] == 0) {
      |         ~~~~~~~~~^~~~
/usr/include/c++/14/bits/regex.h:1441:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator==(const sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)'
 1441 |     operator==(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1441:5: note:   template argument deduction/substitution failed:
a.cc:15:18: note:   '__gnu_cxx::__alloc_traits<std::allocator<mod::MInt<long long int, 998244353> >, mod::MInt<long long int, 998244353> >::value_type' {aka 'mod::MInt<long long int, 998244353>'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   15 |     if (lazy_[k] == 0) {
      |         ~~~~~~~~~^~~~
/usr/include/c++/14/bits/regex.h:1534:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator==(const typename std::iterator_traits<_Iter>::value_type&, const sub_match<_BiIter>&)'
 1534 |     operator==(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1534:5: note:   template argument deduction/substitution failed:
a.cc:15:18: note:   mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'int'
   15 |     if (lazy_[k] == 0) {
      |         ~~~~~~~~~^~~~
/usr/include/c++/14/bits/regex.h:1613:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator==(const sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type&)'
 1613 |     operator==(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1613:5: note:   template argument deduction/substitution failed:
a.cc:15:18: note:   '__gnu_cxx::__alloc_traits<std::allocator<mod::MInt<long long int, 998244353> >, mod::MInt<long long int, 998244353> >::value_type' {aka 'mod::MInt<long long int, 998244353>'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   15 |     if (lazy_[k] == 0) {
      |         ~~~~~~~~~^~~~
/usr/include/c++/14/bits/regex.h:2186:5: note: candidate: 'template<class _Bi_iter, class _Alloc> bool std::__cxx11::operator==(const match_results<_BiIter, _Alloc>&, const match_results<_BiIter, _Alloc>&)'
 2186 |     operator==(const match_results<_Bi_iter, _Alloc>& __m1,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:2186:5: note:   template argument deduction/substitution failed:
a.cc:15:18: note:   '__gnu_cxx::__alloc_traits<std::allocator<mod::MInt<long long int, 998244353> >, mod::MInt<long long int, 998244353> >::value_type' {aka 'mod::MInt<long long int, 998244353>'} is not derived from 'const std::__cxx11::match_results<_BiIter, _Alloc>'
   15 |     if (lazy_[k] == 0) {
      |         ~~~~~~~~~^~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:64,
                 from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51:
/usr/include/c++/14/bits/stl_pair.h:1033:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator==(const pair<_T1, _T2>&, const pair<_T1, _T2>&)'
 1033 |     operator==(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_pair.h:1033:5: note:   template argument deduction/substitution failed:
a.cc:15:18: note:   '__gnu_cxx::__alloc_traits<std::allocator<mod::MInt<long long int, 998244353> >, mod::MInt<long long int, 998244353> >::value_type' {aka 'mod::MInt<long long int, 998244353>'} is not derived from 'const std::pair<_T1, _T2>'
   15 |     if (lazy_[k] == 0) {
      |         ~~~~~~~~~^~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:67:
/usr/include/c++/14/bits/stl_iterator.h:441:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator==(const reverse_iterator<_Iterator>&, const reverse_iterator<_Iterator>&)'
  441 |     operator==(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:441:5: note:   template argument deduction/substitution failed:
a.cc:15:18: note:   '__gnu_cxx::__alloc_traits<std::allocator<mod::MInt<long long int, 998244353> >, mod::MInt<long long int, 998244353> >::value_type' {aka 'mod::MInt<long long int, 998244353>'} is not derived from 'const std::reverse_iterator<_Iterator>'
   15 |     if (lazy_[k] == 0) {
      |         ~~~~~~~~~^~~~
/usr/include/c++/14/bits/stl_iterator.h:486:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator==(const reverse_iterator<_Iterator>&, const reverse_iterator<_IteratorR>&)'
  486 |     operator==(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:486:5: note:   template argument deduction/substitution failed:
a.cc:15:18: note:   '__gnu_cxx::__alloc_traits<std::allocator<mod::MInt<long long int, 998244353> >, mod::MInt<long long int, 998244353> >::value_type' {aka 'mod::MInt<long long int, 998244353>'} is not derived from 'const std::reverse_iterator<_Iterator>'
   15 |     if (lazy_[k] == 0) {
      |         ~~~~~~~~~^~~~
/usr/include/c++/14/bits/stl_iterator.h:1667:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator==(const move_iterator<_IteratorL>&, const move_iterator<_IteratorR>&)'
 1667 |     operator==(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1667:5: note:   template argument deduction/substitution failed:
a.cc:15:18: note:   '__gnu_cxx::__alloc_traits<std::allocator<mod::MInt<long long int, 998244353> >, mod::MInt<long long int, 998244353> >::value_type' {aka 'mod::MInt<long long int, 998244353>'} is not derived from 'const std::move_iterator<_IteratorL>'
   15 |     if (lazy_[k] == 0) {
      |         ~~~~~~~~~^~~~
/usr/include/c++/14/bits/stl_iterator.h:1737:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator==(const move_iterator<_IteratorL>&, const move_iterator<_IteratorL>&)'
 1737 |     operator==(const move_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1737:5: note:   template argument deduction/substitution failed:
a.cc:15:18: note:   '__gnu_cxx::__alloc_traits<std::allocator<mod::MInt<long long int, 998244353> >, mod::MInt<long long int, 998244353> >::value_type' {aka 'mod::MInt<long long int, 998244353>'} is not derived from 'const std: