#include <string.h> #include <algorithm> #include <array> #include <bitset> #include <cassert> #include <chrono> #include <ciso646> #include <climits> #include <cmath> #include <complex> #include <cstdio> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <numeric> #include <optional> #include <queue> #include <random> #include <set> #include <stack> #include <string> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> #define REP_OVERLOAD(arg1, arg2, arg3, arg4, NAME, ...) NAME #define REP3(i, l, r, s) \ for (int i = int(l), rep3_r = int(r), rep3_s = int(s); i < rep3_r; \ i += rep3_s) #define REP2(i, l, r) REP3(i, l, r, 1) #define REP1(i, n) REP2(i, 0, n) #define rep(...) REP_OVERLOAD(__VA_ARGS__, REP3, REP2, REP1, )(__VA_ARGS__) #define repin(i, l, r) for (int i = int(l), repin_r = int(r); i <= repin_r; ++i) #define RREP_OVERLOAD(arg1, arg2, arg3, arg4, NAME, ...) NAME #define RREP3(i, l, r, s) \ for (int i = int(r) - 1, rrep3_l = int(l), rrep3_s = int(s); i >= rrep3_l; \ i -= rrep3_s) #define RREP2(i, l, r) RREP3(i, l, r, 1) #define RREP1(i, n) RREP2(i, 0, n) #define rrep(...) RREP_OVERLOAD(__VA_ARGS__, RREP3, RREP2, RREP1, )(__VA_ARGS__) #define rrepin(i, l, r) \ for (int i = int(r), rrepin_l = int(l); i >= rrepin_l; --i) #define fi first #define se second #include <atcoder/fenwicktree> #include <atcoder/modint> #include <atcoder/modint> #include <vector> namespace rklib { template <class T> struct Factorial { public: Factorial() : Factorial(0) {} Factorial(int n) { fc.resize(n + 1); inv_fc.resize(n + 1); fc[0] = 1; for (int i = 0; i < n; ++i) fc[i + 1] = fc[i] * (i + 1); inv_fc[n] = 1 / fc[n]; for (int i = n - 1; i >= 0; --i) inv_fc[i] = inv_fc[i + 1] * (i + 1); } T fact(int n) { if (n >= (int)fc.size()) extend(n); return fc[n]; } T inv_fact(int n) { if (n >= (int)fc.size()) extend(n); return inv_fc[n]; } T inv(int n) { assert(n > 0); if (n >= (int)fc.size()) extend(n); return inv_fc[n] * fc[n - 1]; } T comb(int n, int r) { if (n < r || r < 0) return 0; if (n >= (int)fc.size()) extend(n); return fc[n] * inv_fc[r] * inv_fc[n - r]; } T perm(int n, int r) { if (n < r || r < 0) return 0; if (n >= (int)fc.size()) extend(n); return fc[n] * inv_fc[n - r]; } private: std::vector<T> fc; std::vector<T> inv_fc; void extend(int n) { int l = fc.size(); int r = l; while (r <= n) r *= 2; fc.resize(r); inv_fc.resize(r); for (int i = l; i < r; ++i) fc[i] = fc[i - 1] * i; inv_fc[r - 1] = 1 / fc[r - 1]; for (int i = r - 2; i >= l; --i) inv_fc[i] = inv_fc[i + 1] * (i + 1); } }; } // namespace rklib #include <algorithm> #include <cassert> #include <vector> namespace rklib { template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; } template <class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; } template <class T> bool chmin_non_negative(T &a, const T &b) { if (a < 0 || a > b) { a = b; return true; } return false; } template <class T> T div_floor(T num, T den) { if (den < 0) num = -num, den = -den; return num >= 0 ? num / den : (num + 1) / den - 1; } template <class T> T div_ceil(T num, T den) { if (den < 0) num = -num, den = -den; return num <= 0 ? num / den : (num - 1) / den + 1; } } // namespace rklib using namespace std; using namespace rklib; using lint = long long; using pii = pair<int, int>; using pll = pair<lint, lint>; using mint = atcoder::modint998244353; int main() { int n, m; scanf("%d%d", &n, &m); int a[n]; fill(a, a + n, -1); bool used[n]; memset(used, false, sizeof(used)); rep(i, m) { int p, k; scanf("%d%d", &p, &k); --p; --k; a[k] = p; used[p] = true; } mint ans = 0; Factorial<mint> fc(n); if (n - m >= 2) { ans += fc.comb(n - m, 2) * fc.comb(n - m, 2) * fc.fact(n - m - 2); } { atcoder::fenwick_tree<int> ft(n); rep(i, n) { if (a[i] == -1) continue; ans += ft.sum(a[i] + 1, n) * fc.fact(n - m); ft.add(a[i], 1); } } vector<int> yet; rep(i, n) if (!used[i]) yet.push_back(i); int vacant = 0; rep(i, n) { if (a[i] == -1) { ++vacant; continue; } mint tmp = 0; tmp += mint(vacant) * (yet.end() - upper_bound(yet.begin(), yet.end(), a[i])); tmp += mint(n - m - vacant) * (lower_bound(yet.begin(), yet.end(), a[i]) - yet.begin()); ans += tmp * fc.fact(n - m - 1); } printf("%u\n", ans.val()); }