对于一个非空子集 $S$，其所有元素的最小公倍数为 $2^{\max_{j \in S} a_j} \times 3^{\max_{j \in S} b_j}$。

如果我们直接枚举子集，复杂度将是 $O(2^n)$，显然无法接受。我们可以改变思路：按最大值元素进行归类计算。

将所有元素按照 $a_i$ 升序排列；如果 $a_i$ 相同，则按 $b_i$ 升序排列。

排序后，我们假设子集中最靠后的元素下标为 $i$。那么由于排序的性质，该子集的最大 $a$ 值必定为 $a_i$。

这就把所有的非空子集完美划分成了 $n$ 个不重不漏的类：对于固定的 $i$，子集必定包含元素 $i$，且其余元素只能从 $1$ 到 $i-1$ 中选取。

当最大元素下标固定为 $i$ 时，该子集的 $a$ 维度最大值是 $a_i$。那么 $b$ 维度的最大值是什么呢？

包含元素 $i$ 的子集 $b$ 维度的最大值为 $\max(b_i, \max_{j \in S \{i\}} b_j)$。

我们需要在所有由 $\{1, 2, \dots, i-1\}$ 组成的子集中，对 $3^{\max(b_i, \dots)}$ 求和。

我们将前 $i-1$ 个元素的 $b$ 值集合记为 $B$。对于 $B$ 中的元素：

• 所有 $\le b_i$ 的元素，无论是否选入子集，都不会超过 $b_i$。如果共有 $c$ 个这样的元素，它们会产生 $2^c$ 种组合，对这 $2^c$ 种子集而言，$b$ 的最大值均为 $b_i$。
• 对于 $B$ 中 $> b_i$ 的元素，如果选了它们，最大值就会由它们决定。我们将 $B$ 中 $> b_i$ 的元素从小到大排列，如果子集中的最大值恰好排在第 $k$ 位（即前面有 $k-1$ 个比它小的数），那么共有 $2^{k-1}$ 种子集能以它为最大值。

使用一棵线段树，以离散化后的 $b$ 值为下标，动态维护集合 $B$ 中元素的分布情况。线段树的每个节点维护两个值：

• cnt：区间内当前存在的元素个数。
• val：区间内所有元素若作为最大值时，提供的权值之和，即 $\sum 2^{k-1} 3^{v_k} \pmod{10^9+7}$。

$up$ 时，左子树的元素一定小于右子树的元素。因此，右子树中的元素在整个区间内排名时，前面会额外多出左子树的 cnt 个元素。

$$cnt = left.cnt + right.cnt$$ $$val = (left.val + right.val * 2^{left.cnt}) \pmod{10^9+7}$$

以样例 $1$ 为例：3 个数，分别为 (1, 2), (2, 1), (1, 2)。

排序后：1: (1,2)、2: (1,2)、3: (2,1)。

• 处理第 1 个数 (1, 2)：当前树为空，$c=0$。大于 $b_i=2$ 的部分也为空。该数构成的组合值为 $2^0 \times 3^2 = 9$。乘以 $2^{a_1}$ 得到 $2^1 \times 9 = 18$。将 $b=2$ 插入线段树，线段树中 b=2 节点 cnt=1, val=9。总和 ans = 18。
• 处理第 2 个数 (1, 2)：查询 $\le 2$ 的元素个数 $c=1$。大于 $2$ 的部分为空。组合值为 $2^1 \times 3^2 = 18$。乘以 $2^{a_2}$ 得到 $2^1 \times 18 = 36$。将 $b=2$ 再次插入线段树，此时 b=2 节点 cnt=2，利用合并公式 val = 9 + 9 * 2^1 = 27。总和 ans = 18 + 36 = 54。
• 处理第 3 个数 (2, 1)：查询 $\le 1$ 的元素个数 $c=0$。大于 $1$ 的部分有 b=2 的节点，其返回 val=27。组合值为 $2^0 \times (3^1 + 27) = 30$。乘以 $2^{a_3}$ 得到 $2^2 \times 30 = 120$。将 $b=1$ 插入线段树。总和 ans = 54 + 120 = 174。