\(i=1,2,\ldots, N-1\) ぞれぞれについて、 チーム \(A\) が \(i\) 人、チーム \(B\) が \((N-i)\) 人となるようなチーム分けのうち条件をみたすものがいくつあるかについて考えます。最終的に求める値はそれらの和となります。

選手 \(j=1,2,\ldots, N\) は以下の \(4\) つのいずれかに分類できます。

• グループ \(1\): \(L_j\leq i\leq R_j\) かつ \(L_j\leq (N-i)\leq R_j\) であるとき、選手 \(j\) はチーム \(A,B\) のいずれにも所属できる。
• グループ \(2\): \(L_j\leq i\leq R_j\) であるが、 \(L_j\leq (N-i)\leq R_j\) でないとき、選手 \(j\) はチーム \(A\) にのみ所属できる。
• グループ \(3\): \(L_j\leq i\leq R_j\) でないが、 \(L_j\leq (N-i)\leq R_j\) であるとき、選手 \(j\) はチーム \(B\) にのみ所属できる。
• グループ \(4\): \(L_j\leq i\leq R_j\) でも \(L_j\leq (N-i)\leq R_j\) でもないとき、選手 \(j\) はチーム \(A,B\) のいずれにも所属できない。

このとき、以下の条件のうち一つでもみたされる場合、この \(i\) について条件をみたす分け方は存在しません。

• グループ \(2\) に属する選手が \((i+1)\) 人以上存在する。
• グループ \(3\) に属する選手が \((N-i+1)\) 人以上存在する。
• グループ \(4\) に属する選手が \(1\) 人でも存在する。

これは、各選手がいずれかのチームに属さなければならないこと、およびチーム \(A,B\)　がそれぞれちょうど \(i,(N-i)\) 人からなる必要があることから従います。

そうで無い場合、グループ \(1,2,3\) に属する人数を \(X_{i,1},X_{i,2},X_{i,3}\) （仮定よりグループ \(4\) に属する選手はいないため \(X_{i,1}+X_{i,2}+X_{i,3}=N\)）とすると、条件をみたすように分けるためには、チーム \(A\) にグループ \(2\) に属する全員に加えて、グループ \(1\) に属する \(X_{i,1}\) 人のうち \((i-X_{i,2})\) 人が属し、チーム \(B\) にはグループ \(3\) に属する全員とグループ \(1\) のうち残りの \(X_{i,1}-(i-X_{i,2})=(N-i-X_{i,3})\) 人が属するようにするようにすることが必要十分です。よって、このとき、条件をみたす分け方は

\[ \binom{X_{i,1}}{i-X_{i,2}}=\frac{X_{i,1}!}{(i-X_{i,2})!~(N-i-X_{i,3})!} \]

通りあります。ここで \(\binom{n}{k}\) は二項係数を表します。
答えは、先に述べたようにこれを \(i=1,2,\ldots,N-1\) について足し合わせあまりを取ることによって求められます。

\(X_{i,1}\) は高々 \(N\) であるため、\(k=0,1,\ldots,N\) について \(k!\) およびその逆数の \(\pmod{998244353}\) での値を前計算しておくことで、それぞれの \(i\) に対して \(O(1)\) で計算できます。

また、\(X_{i,1}, X_{i,2}, X_{i,3}\) は各 \(i\) について愚直に計算すると、全体で \(O(N^2)\) の時間がかかってしまいますが、\(i\) について昇順に求めることを考えると、選手 \(j\) の属するグループが変わるタイミングは \(i=L_j-1\to L_j\), \(R_j\to R_j+1\), \((N-R_j-1)\to(N-R_j)\), \((N-L_j)\to (N-L_j+1)\) の高々 \(4\) 回しかありません。よって、それぞれの \(i\) について、\(i-1\to i\) で属するグループが変わる選手についてのみ、その選手がどのグループからどのグループへ移動したか求めることで全体で \(O(N)\) で計算できます。

前計算にかかる時間が \(O(N\log P)\) （今回は \(P=998244353\) ）、\(X_{i,1}, X_{i,2}, X_{i,3}\)　の計算および分け方の計算について \(O(N)\) の時間がかかるため、全体で \(O(N\log P)\) でこの問題を解くことができます。
よって、この問題を解くことができました。

C++による実装例:

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using namespace atcoder;

using mint = modint998244353;

#define N (int)3e+5
#define rep(i, n) for(int i = 0; i < n; ++i)

mint frac[N+1];

void pre_calc(void){
	frac[0]=mint(1);
	for(int i=1;i<=N;i++){
		frac[i]=frac[i-1]*mint(i);
	}
	return;
}

mint binom(int x,int y){
	if(x<0)return mint(0);
	if(y<0)return mint(0);
	if(y>x)return mint(0);
	return frac[x]*(frac[y].inv())*(frac[x-y].inv());
}

int main(void){
	int n;
	int l[N],r[N];
	int aok[N]={},bok[N]={};
	int m[2][2]={};
	vector<int>cand[N];
	mint ans=mint(0);
	cin>>n;
	rep(i,n){
		cin>>l[i]>>r[i];
		cand[l[i]].push_back(i);
		cand[r[i]+1].push_back(i);
		cand[n-l[i]+1].push_back(i);
		cand[n-r[i]].push_back(i);
	}
	m[0][0]=n;

	pre_calc();
	for(int i=1;i<=n-1;i++){
		int sz=cand[i].size();
		rep(j,sz){
			int z=cand[i][j];
			m[aok[z]][bok[z]]--;
			if((l[z]<=i)&&(i<=r[z]))aok[z]=1;
			else aok[z]=0;
			if((l[z]<=(n-i))&&((n-i)<=r[z]))bok[z]=1;
			else bok[z]=0;
			m[aok[z]][bok[z]]++;
		}
		if((m[0][0]==0)&&(m[1][0]<=i)&&(m[0][1]<=(n-i))){
			ans+=binom(m[1][1],i-m[1][0]);
		}
	}
	cout<<ans.val()<<endl;
}