题目描述

Eunectes 要打一场大战。 她的初始力量值为 $0$，大战前，她会吃 $n$ 个食物，吃下食物会获得以下两种效果之一：

1. 力量值增加 $x$。
2. 力量值乘以 $x$。

Eunectes 可以自由决定食物的食用顺序，她想知道能获得的最大力量值是多少，答案对 $10^9 + 7$ 取模。

输入格式

第一行一个正整数 $n$。 接下来 $n$ 行，每行两个正整数 $type, x$。

• 若 $type = 1$ 表示吃下该食物后力量值增加 $x$；
• 若 $type = 2$ 表示吃下该食物后力量值乘以 $x$；

输出格式

输出一行一个整数，表示答案。

输入输出样例

样例解释

• 第一个样例：$(0 + 2) \times 3 = 6$
• 第二个样例：$0 \times 1 \times 2 \times 3 = 0$
• 第三个样例：$(0 + 1 + 2) \times 3 = 9$

数据范围

• 对于 $20\%$ 的数据，保证所有的 $type = 1$。
• 对于另外的 $10\%$ 的数据，保证所有的 $type = 2$。
• 对于 $100\%$ 的数据，保证 $1 \leqslant n \leqslant 10^5$，$1 \leqslant x \leqslant 10^9$，$type \in \{1, 2\}$。