Description

本题的简单版是 2024 年趣味赛第一场 C 题，该版本与简单版的区别在于猫猫虫的类型、数据范围以及输出要求的不同。

在遥远的大洋彼岸，矗立着一座猫猫城，猫猫城里住着许多猫猫虫。

和人类社会一样，猫猫虫也是有领导猫的，并且每隔一段时间都会举行一场盛大的猫猫城大选。今年的大选即将开始。

猫猫城的现任领导猫，Capoo，希望能够蝉联猫猫城领导猫的席位，因此它想在大选开始前进行一次民意调查。

在此次民意调查中，猫猫城的每个公民都拥有投票的权利，它们可以根据自己的意愿选择是否支持 Capoo 继续担任猫猫城的领导猫。Capoo 希望自己的支持率大于 $50\%$。

有的猫猫虫有自己坚定的想法，然而让有的猫猫虫做出自己的决定是一件很困难的事情，因此它们都会有从众心理或者逆反心理。具体地，现在猫猫城里一共有 $n$ 只猫猫虫（不包含 Capoo，很显然 Capoo 并不能给自己投票），对于第 $i$ 只猫猫虫，它将属于以下四种类型当中的一种：

1. 无条件投出支持票；
2. 无条件投出反对票；
3. 如果支持数大于反对数，那么它将投下支持票；如果支持数小于反对数，那么它将投下反对票；如果支持数等于反对数，那么它将有 $p_i$ 的概率投下支持票，$1-p_i$ 的概率投下反对票；
4. 如果支持数大于反对数，那么它将投下反对票；如果支持数小于反对数，那么它将投下支持票；如果支持数等于反对数，那么它将有 $p_i$ 的概率投下支持票，$1-p_i$ 的概率投下反对票。

Capoo 希望能够预测调查的结果，因此它前来求助大魔法师波波王。波波王使用读心术看出了每一只猫猫虫属于哪种类型。现在 Capoo 想知道，在所有 $n$ 只猫猫虫按顺序投完票后，支持数减去反对数的期望是多少，对 $998244353$ 取模。

Input

第一行一个整数 $n$（$1\leq n \leq 10^6$），表示猫猫城里猫猫虫的数量，不包含 Capoo 自己。

接下来 $n$ 行，第 $i$ 行两个数，描述第 $i$ 只投票的猫猫虫。一个整数 $a_i$（$a_i\in\{1,2,3,4\}$），表示第 $i$ 只猫猫虫属于上述描述中的哪个类型；一个整数 $p_i$（$0\leq p_i< 998244353$），题目中保证所有出现的概率为有理数，记与这只猫猫虫有关的概率为 $\frac{x_i}{y_i}$，其中 $x_i$ 为非负整数，$y_i$ 为正整数，则给出的 $p_i$ 为 $x_i\cdot y_i^{-1}\bmod 998244353$，其中 $y_i^{-1}$ 表示 $y_i$ 在模 $998244353$ 意义下的逆元。保证若 $a_i=1$，则 $p_i=1$；若为 $a_i=2$，则 $p_i=0$。

Output

一行一个整数，表示支持数减去反对数的期望，对 $998244353$ 取模。可以证明这个期望是一个有理数，记为 $\frac{p}{q}$，你要输出的答案为 $p\cdot q^{-1}\bmod 998244353$，其中 $q^{-1}$ 表示 $q$ 在模 $998244353$ 意义下的逆元。

Samples

2
3 1
4 114514

0

Note

对于样例，显然第一只猫猫虫一定会投下支持票，第二只猫猫虫一定会投下反对票，因此支持票减去反对票的数量为 $0$。

Resources

The 23rd UESTC Programming Contest Preliminary