#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); vi l(Q), r(Q); rep(i,0,Q){ ll L,R; cin >> L >> R; sum[L-1] ^= (1ll< set; rep(i,0,Q) set.insert(l[i]-1), set.insert(r[i]); set.insert(0); set.insert(N); vi data(ALL(set)); ll cnt2 = 0; rep(i,1,data.size()){ ll length = data[i]-data[i-1]; if(length%2) cnt2++; } if(cnt2 > 1) ans = 0; } rep(i,0,N) sum[i+1] ^= sum[i]; std::map cnt; rep(i,0,N) cnt[sum[i]]++; for(auto el: cnt){ if(el.second%2){ 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; }