4452. 果蝇炸弹

【题目背景】

果蝇王前来视察机房里的蜜雪冰城。

【题目描述】

机房里有 $n$ 杯蜜雪排成一行，第 $i$ 杯蜜雪位于 $a_i$ 的位置。每杯蜜雪冰城里都挤着一大群果蝇，一旦其被打开，里面的果蝇就会喷发而出，影响周围 $r_i$ 的区域。具体地，第 $i$ 杯蜜雪打开后会影响 $[a_i-r_i,a_i+r_i]$ 的区域。若一杯蜜雪被果蝇影响，其自身也会炸开。

果蝇王决定选择一个蜜雪子集（可能为空），并同时打开集合内的蜜雪，它想知道，一共有多少种可能的结果？两种结果不同当且仅当最终打开的蜜雪集合不同。由于答案可能很大，你只需输出其对 $10^9+7$ 取模的结果。

【输入格式】

第一行一个数 $c$ 表示测试点编号

第二行一个数 $n$。

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

【输出格式】

输出可能的结果数对 $10^9+7$ 取模的结果。

【样例输入】

0
4
0 2
2 0
3 2
7 4

【样例输出】

7

【数据规模与约定】

与 COGS 常规题目不同的是，本题采用捆绑测试。

捆绑测试介绍：将若干个满足同一约定的不同数据点捆绑成一个 Subtask，按照 Subtask 计分，你必须拿到这个 Subtask 下的全部数据点的 Accepted 才能拿到这个 Subtask 的分数，若你在某 Subtask 下有至少一个数据点没有得到 Accepted，此 Subtask 你的分数记为 0 分。

$n\le 16$：$10$ 分，对应第一个测试点。

$n\le 5000$：$50$ 分，对应 $2\sim 6$ 测试点。

无特殊限制：$40$ 分，对应 $7\sim 10$ 测试点。

对于所有数据，均有 $1\le n\le 3\times 10^5$，$0\le a_i,r_i\le 10^{18}$。保证 $a$ 数组严格递增。

大样例

【来源】

luogu P9100