现在有 n 个数，其中第 i 个数等于 2^a[i]×3^b[i] 。

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

第一行，一个整数 n 。

接下来 n 行，每行两个整数 a[i],b[i] 。

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

3
1 2
2 1
1 2

174

数据规模
共 10 组数据。
测试点 1,2 满足 n≤20 。
测试点 3,4 满足 a[i],b[i]≤1000 。
测试点 5,6 满足 n≤1000 。
对于 100%的数据，满足 1≤n≤10^5, 0≤a[i]≤b[i]≤10^9 。