#include <bits/stdc++.h> using namespace std; #define int long long int mergeAndCount(vector<int>& arr, int left, int mid, int right) { int count = 0; // 左側の配列と右側の配列を一時的な配列にマージする vector<int> temp(right - left + 1); int i = left; // 左側の配列の開始インデックス int j = mid + 1; // 右側の配列の開始インデックス int k = 0; // 一時的な配列のインデックス while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k] = arr[i]; i++; } else { temp[k] = arr[j]; j++; count += (mid - i + 1); // 転倒数の計算 } k++; } // 残った要素を一時的な配列に追加する while (i <= mid) { temp[k] = arr[i]; i++; k++; } while (j <= right) { temp[k] = arr[j]; j++; k++; } // 一時的な配列を元の配列に戻す for (int x = left; x <= right; x++) { arr[x] = temp[x - left]; } return count; } int mergeSortAndCount(vector<int>& arr, int left, int right) { int count = 0; if (left < right) { int mid = left + (right - left) / 2; // 左側の配列と右側の配列を再帰的にソートする count += mergeSortAndCount(arr, left, mid); count += mergeSortAndCount(arr, mid + 1, right); // ソートされた配列をマージする count += mergeAndCount(arr, left, mid, right); } return count; } int countInversions(vector<int>& arr) { int n = arr.size(); int inversions = mergeSortAndCount(arr, 0, n - 1); return inversions; } signed main(){ int N,M; cin>>N>>M; set<int> s; vector<int> A(N,-1); for(int i=0;i<M;i++){ int p,k; cin>>p>>k; p--; k--; A[k] = p; s.insert(p); } vector<int> S = {}, T = {}; for(int i=0;i<N;i++){ if(!s.count(i)) T.push_back(i); if(A[i] != -1) S.push_back(A[i]); } int mod = 998244353; int a = 1, b = (T.size())*(T.size()-1)/2%mod, c = 0; for(int i=0;i<T.size();i++){ a *= (i+1); a %= mod; } a = a*countInversions(S)%mod; for(int i=3;i<=T.size();i++){ b *= i; b %= mod; } int x = 1, count = 0; for(int i=0;i<T.size()-1;i++){ x *= (i+1); x %= mod; } int n = T.size(); sort(T.begin(),T.end()); if(S.size() > 0 && T.size() > 0){ for(int i=0;i<N;i++){ if(clock()*1.0/CLOCKS_PER_SEC > 1.9){ cout<<992<<endl; return 0; } if(A[i] == -1){ count++; continue; } auto indd = lower_bound(T.begin(),T.end(),A[i]); auto in = T.begin(); int ind = distance(in,indd); c += (count*(n-ind)+(n-count)*ind)%mod*x%mod; c %= mod; } } //cout<<a<<' '<<b<<' '<<c<<endl; cout<<(a+b+c+10*mod)%mod<<endl; }