题目描述

现在有 $n$ 个数，其中第 $i$ 个数等于 $2^{a_i} \times 3^{b_i}$。

对所有的非空子集，求出它们的最小公倍数，并且求和。求这个和对 $10^9 + 7$ 取模的结果。

输入格式

第一行，一个整数 $n$。

接下来 $n$ 行，每行两个整数 $a_i, b_i$。

输出格式

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

输入输出样例 #1

输入 #1

3
1 2
2 1
1 2

输出 #1

174

说明/提示

共 10 组数据。

• 测试点 1, 2 满足 $n \le 20$。
• 测试点 3, 4 满足 $a_i, b_i \le 1000$。
• 测试点 5, 6 满足 $n \le 1000$。

对于 $100\%$ 的数据，满足 $1 \le n \le 10^5$, $0 \le a_i, b_i \le 10^9$。