Problem: Snuke found a random number generator. It generates an integer between 0 and N-1 (inclusive). An integer sequence A_0, A_1, \cdots, A_{N-1} represents the probability that each of these integers is generated. The integer i (0 \leq i \leq N-1) is generated with probability A_i / S, where S = \sum_{i=0}^{N-1} A_i. The process of generating an integer is done independently each time the generator is executed.

Now, Snuke will repeatedly generate an integer with this generator until the following condition is satisfied:

* For every i (0 \leq i \leq N-1), the integer i has been generated at least B_i times so far.



Find the expected number of times Snuke will generate an integer, and print it modulo 998244353. More formally, represent the expected number of generations as an irreducible fraction P/Q. Then, there exists a unique integer R such that R \times Q \equiv P \pmod{998244353},\ 0 \leq R < 998244353, so print this R.

From the constraints of this problem, we can prove that the expected number of generations is a finite rational number, and its integer representation modulo 998244353 can be defined.

Constraints

* 1 \leq N \leq 400
* 1 \leq A_i
* \sum_{i=0}^{N-1} A_i \leq 400
* 1 \leq B_i
* \sum_{i=0}^{N-1} B_i \leq 400
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
A_0 B_0
A_1 B_1
\vdots
A_{N-1} B_{N-1}


Output

Print the expected number of times Snuke will generate an integer, modulo 998244353.

Examples

Input

2
1 1
1 1


Output

3


Input

3
1 3
2 2
3 1


Output

971485877


Input

15
29 3
78 69
19 15
82 14
9 120
14 51
3 7
6 14
28 4
13 12
1 5
32 30
49 24
35 23
2 9


Output

371626143

Solution (in CPP):

Solution:
/*
{By GWj
*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define R(a) cin>>a
#define R2(a,b) cin>>a>>b
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
LL n,a[404],b[404];
const int MOD=998244353;
LL sum=0,fact[404],rfact[404];
LL quick(LL A,LL B){
	if(!B) return 1ll;
	LL tmp=quick(A,B>>1);
	tmp*=tmp;
	tmp%=MOD;
	if(B&1){
		tmp*=A;
		tmp%=MOD;
	}
	return tmp;
}
LL c(LL A,LL B){
	return fact[B]*rfact[A]%MOD*rfact[B-A]%MOD;
} 
LL dp[404][404][404][2],g[404][404][2]; 
LL inv[404][404],mi[404][404]/*(i^j)^(-1)*/;
int main(){
	fastio;
	R(n);
	LL sum2=0;
	rb(i,1,n){
		R2(a[i],b[i]); 
		sum2+=b[i];
		sum+=a[i];
	} 
	fact[0]=1ll;
	rb(i,1,400)
		fact[i]=fact[i-1]*i%MOD;
	rfact[400]=quick(fact[400],MOD-2);
	rfact[0]=1;
	rl(i,399,1){
		rfact[i]=rfact[i+1]*(i+1)%MOD;
	}
	rb(i,0,400)
		rb(j,0,400)
			inv[i][j]=quick(quick(i,j),MOD-2),mi[i][j]=quick(i,j);
	g[0][0][0]=1;
	rb(i,1,n){
		rb(k,0,b[i]-1)
			rb(s,a[i],400){
				rb(x,k,400){
					rep(p,2){
						if(!g[s-a[i]][x-k][p^1]) continue;
						dp[i][s][x][p]+=g[s-a[i]][x-k][p^1]*rfact[x-k]%MOD*fact[x]%MOD*mi[s-a[i]][x-k]%MOD*inv[s][x]%MOD*mi[a[i]][k]%MOD*rfact[k]%MOD*(s-a[i]? (s-a[i])*inv[s][1]%MOD:sum*inv[s][1]%MOD)%MOD;
						dp[i][s][x][p]%=MOD;						
					}
				}
			}
		rb(s,0,400)
			rb(x,0,400)
				rep(p,2)
					g[s][x][p]+=dp[i][s][x][p],g[s][x][p]%=MOD;
	}
	LL rest=0;
	rb(s,0,400)
		if(s)
		rb(x,0,400)
			rep(p,2){
				if(p){
					rest+=g[s][x][p];
					rest%=MOD;		
				}
				else{
					rest-=g[s][x][p];
					rest+=MOD;
					rest%=MOD;
				}
			}
//	cout<<9ll*inv[2][1]%MOD<<endl;
	cout<<rest<<endl;
	return 0;
}
/*
2
1 2
1 1

*/