最小公倍数

题目描述 现在有�个数，其中第�个数等于2�� × 3�� 。

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

输入格式 第一行，一个整数�。

接下来�行，每行两个整数�� , ��。

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

样例输入 1 3 1 2 2 1 1 2

样例输出 1 174

样例输入输出 2 见下发文件。

数据规模 共 10 组数据。

测试点 1,2 满足� ≤ 20。

测试点 3,4 满足�� , �� ≤ 1000。

测试点 5,6 满足� ≤ 1000。

对于 100%的数据，满足 1 ≤ � ≤ 105 , 0 ≤ �� ≤ �� ≤ 109 。