AT_pakencamp_2018_day3_f ミックスジュース

为了参加「KACoder」舞蹈编程盛会，ぬけす君决定在预选赛前的 $ Q $ 天里每天喝一种精灵混合果汁，这种果汁据说对身体有益。每只精灵的「美味度」是一个正整数，混合果汁的「美味度」则是所有选用精灵美味度的总和。 在每一个早晨，你能采购到美味度在 $ A_i $ 到 $ B_i $ 范围内的精灵各一只，并可以从中选择一只或多只投入搅拌机制作果汁。需要注意的是，由于新鲜度要求，未使用的精灵当天晚上会被丢弃，不能再使用。 你的任务是计算第 $ i $ 天能制作出的混合果汁的美味度可能有多少种不同的值。由于答案可能非常大，请输出结果对 $ 10^9+7 $ 取模后的值。

输入数据从标准输入读取，格式如下： 第 $ 1 $ 行是一个整数 $ Q $，表示天数。 接下来的 $ Q $ 行中，第 $ i $ 行包含两个整数 $ A_i $ 和 $ B_i $，分别表示第 $ i $ 天早晨可采购的精灵美味度的下限与上限。

请输出 $ Q $ 行，每行一个整数，表示对应的那一天能制作出的混合果汁的美味度的不同值的总数。

- $ 1 \leq Q \leq 100000 $ - $ 1 \leq A_i \leq B_i \leq 10^9 $ ### 子任务 1. 子任务 1 \[$ 7 $ 分\]: $ Q = 1 $，且 $ B_1 - A_1 \leq 20 $。 2. 子任务 2 \[$ 60 $ 分\]: 所有 $ B_i - A_i $ 之和不超过 $ 10^6 $。 3. 子任务 3 \[$ 33 $ 分\]: 没有进一步的限制。 ### 示例解释 例如，在第 $ 3 $ 天，可选的精灵美味度为 $ 4, 5, 6, 7 $。从中选出一个或多个精灵的组合方式共有 $ 15 $ 种，其结果的美味度分别为 $ 4, 5, 6, 7, 4+5, 4+6, 5+6, 4+7, 5+7, 6+7, 4+5+6, 4+5+7, 4+6+7, 5+6+7, 4+5+6+7 $。其中唯有 $ 5+6 $ 和 $ 4+7 $ 这两种组合让结果相同（都是 $ 11 $），所以真正能产生的不同美味度总共有 $ 14 $ 种。 **本翻译由 AI 自动生成**