32355번 - 택틱

문제

레이는 캐릭터 수집형 게임 '파랑 저장소' 의 플레이어이다. 오늘도 레이는 좋은 등수를 차지하기 위해 보스 타임어택을 열심히 하고 있다. 다른 플레이어보다 빠르게 보스를 잡기 위해서는 좋은 캐릭터를 많이 뽑아야 하지만, 가난한 대학생인 레이는 돈이 없어 좋은 캐릭터를 많이 뽑지 못하였다. 대신에 레이는 보스를 효율적으로 공격할 수 있는 다양한 전략인 택틱을 조합하여 좋은 기록을 내려고 한다.

레이는 밤새 게임 커뮤니티를 열심히 정독하여 총 $N$개의 택틱을 찾았고, $i$ 번째 택틱은 $\dfrac{p_i}{q_i}$의 확률로 성공하거나 1ドル-\dfrac{p_i}{q_i}$의 확률로 실패한다. 택틱은 순서대로 실행되며 레이의 보스 타임어택 점수는 $i$ 번째 택틱이 성공할 경우 $G_i$점 증가하고 실패할 경우 $L_i$점 감소한다.

모든 택틱이 실행되고 난 후의 레이의 보스 타임어택 점수를 $X$라 하자. 만약 $X$가 양수일 경우, 레이는 $X^{2}$ 만큼의 내면의 평화를 얻게 되고 게임을 더 열심히 하게 된다. 하지만 $X$가 음수일 경우 레이는 $X^{2}$ 만큼의 스트레스를 받고 게임을 접을 확률이 증가하게 된다. 열심히 보스 타임어택을 하느라 바쁜 레이를 위해 레이가 얻을 수 있는 내면의 평화와 스트레스의 정보를 계산해 주자.

입력

첫 번째 줄에 택틱의 수 $N$이 주어진다. $(1 \leq N \leq 40)$

두 번째 줄부터 $N$개의 줄에 걸쳐서 $i$번째 택틱이 성공할 확률을 나타내는 두 정수 $p_i,ドル $q_i,ドル 성공 시 얻는 점수 $G_i,ドル 실패 시 잃는 점수 $L_i$가 공백으로 구분되어 주어진다. $(1 \leq p_i < q_i \leq 10^7;$ 1ドル \le G_i, L_i \leq 10^{7})$

주어지는 모든 수는 정수이다.

모든 택틱은 실행되는 순서대로 주어진다.

출력

첫 번째 줄에 모든 택틱이 순서대로 실행되었을 때 내면의 평화를 얻을 확률 $P_1 \bmod 998244353$과 내면의 평화를 얻었을 경우의 평균 $E_1 \bmod 998244353$를 출력한다.

두 번째 줄에 모든 택틱이 순서대로 실행되었을 때 스트레스를 얻을 확률 $P_2 \bmod 998244353$와 스트레스를 얻었을 경우의 평균 $E_2 \bmod 998244353$를 출력한다.

$P_1 \bmod 998244353$과 $P_2 \bmod 998244353$이 0ドル$이 아닌 입력만 주어진다.

분수 $\dfrac{p}{q}$가 있을 때 $\dfrac{p}{q} \bmod 998244353$은 $qu \equiv p \pmod {998244353}$이 되는 0ドル \le u < 998244353$ 범위의 정수 $u$로 정의된다. 모든 출력해야 하는 값은 이러한 정수 $u$가 유일하게 존재함이 보장된다.

제한

힌트