#include #define rep(i, j, n) for(ll i = ll(j); i < ll(n); i++) #define REP(i, j, n) for(ll i = ll(j); i <= ll(n); i++) #define per(i, j, n) for(ll i = ll(j); ll(n) <= i; i--) #define ALL(a) (a).begin(),(a).end() #define revALL(a) (a).rbegin(),(a).rend() #define pb emplace_back #define mp std::make_pair #define mtp std::make_tuple #define ln "\n" using std::endl; using std::cin; using std::cout; using ll = long long; using std::vector; using std::string; using vi = vector; using vii = vector; using pii = std::pair; constexpr ll MOD = 998244353; constexpr ll MAX = 1e6+10; constexpr ll inf = (1ll << 60); //binom_init, binom vi fac,finv,inv; void binom_init() { fac.resize(MAX); finv.resize(MAX); inv.resize(MAX); fac[0] = fac[1] = 1; inv[1] = 1; finv[0] = finv[1] = 1; rep(i, 2, MAX){ fac[i] = fac[i-1]*i%MOD; inv[i] = MOD-MOD/i*inv[MOD%i]%MOD; finv[i] = finv[i-1]*inv[i]%MOD; } } ll binom(ll n, ll r){ if(n> N >> Q; vi sum(N+1); rep(i,0,Q){ ll L,R; cin >> L >> R; sum[L-1] ^= (1< cnt; rep(i,0,N) cnt[sum[i]]++; ll ans = fac[N/2]*fac[N-N/2]%MOD; for(auto el: cnt){ if(el.second%2){ if(el.first) ans = 0; else ans *= binom(el.second+1,(el.second+1)/2)*inv[(el.second+1)/2+1]%MOD; } else ans *= binom(el.second,el.second/2)*inv[el.second/2+1]%MOD; ans %= MOD; } cout << ans << ln; }