2020CCPC绵阳 L. Lottery

绵阳 L. Lottery"/>

2020CCPC绵阳 L. Lottery

题目链接
Little Rabbit walks into a shopping mall and comes across a lottery activity. There are n n n boxes. Inside the i i i-th box, there are x i x_i xi​ balls labeled with 2 a i 2^{a_i} 2ai​. Little Rabbit can pick out any number (including zero) of balls from each box. The sum of numbers on the chosen balls is the score he gets. Whether Little Rabbit wins a prize in the lottery depends on the score.

However, Little Rabbit doesn’t care if he can win a prize. He is curious about how many different scores he is likely to get. Can you help him with it? Since the answer can be very large, please tell him the answer modulo 1 0 9 + 7 10^9+7 109+7.

Input

The first line of the input contains an integer T T T ( 1 ≤ T ≤ 100 1 \le T \le 100 1≤T≤100) — the number of test cases.

In each test case, the first line contains an integer n n n ( 1 ≤ n ≤ 1 0 5 1 \le n \le 10^5 1≤n≤105) — the number of boxes. The sum of n n n will not exceed 1 0 5 10^5 105.

Then in the next n n n lines, the i i i-th line contains two integers a i a_i ai​ ( 0 ≤ a i ≤ 1 0 9 0 \le a_i \le 10^9 0≤ai​≤109) and x i x_i xi​ ( 1 ≤ x i ≤ 1 0 9 1 \le x_i \le 10^9 1≤xi​≤109), which means there are x i x_i xi​ balls numbered 2 a i 2^{a_i} 2ai​ inside the i i i-th box. It’s guaranteed that a 1 , a 2 , … , a n a_1,a_2,\dots,a_n a1​,a2​,…,an​ are all distinct.

Output

For the x x x-th test case, if the answer modulo 1 0 9 + 7 10^9+7 109+7 is y y y, output C a s e Case Case # x x x: y y y in a single line.

Example

input

2
3
1 1
2 1
3 1
3
1 1
2 2
3 3

output

Case #1: 8
Case #2: 18

将幂次按升序排序，然后对于每个 x x x ，如果 x > 2 x>2 x>2 ，则将多余部分其合并到幂次更高的盒子中，最终确保每种幂次的数量在 [ 1 , 2 ] [1,2] [1,2] 中。
定义幂次 u u u 到 v v v 连续：对于 i ∈ [ u , v ] i\in[u,v] i∈[u,v] ， x i ≠ 0 x_i\not =0 xi​​=0 ，且 x u − 1 x_{u-1} xu−1​ 和 x v + 1 x_{v+1} xv+1​ 等于 0 0 0 。
对于连续的一段幂次 x u ⋅ 2 u , x u + 1 ⋅ 2 u + 1 , ⋯ , x v ⋅ 2 v x_u\cdot2^u,x_{u+1}\cdot2^{u+1},\cdots,x_v\cdot2^v xu​⋅2u,xu+1​⋅2u+1,⋯,xv​⋅2v，通过确定每种幂次选择的数量，可以得到 { 0 } ∪ [ 2 u , x u ⋅ 2 u + x u + 1 ⋅ 2 u + 1 + ⋯ + x v ⋅ 2 v ] \{0\}\cup[2^u,x_u\cdot2^u+x_{u+1}\cdot2^{u+1}+\cdots+x_v\cdot2^v] {0}∪[2u,xu​⋅2u+xu+1​⋅2u+1+⋯+xv​⋅2v] 范围内的任何数，且不会影响到其他幂次连续的段，因此统计数量即可，其中 0 0 0 单独统计。

#include<bits/stdc++.h>using namespace std;inline int qr() {int f = 0, fu = 1;char c = getchar();while (c < '0' || c > '9') {if (c == '-')fu = -1;c = getchar();}while (c >= '0' && c <= '9') {f = (f << 3) + (f << 1) + c - 48;c = getchar();}return f * fu;
}const int N = 1e5 + 10, MOD = 1e9 + 7;struct node {int x, a;inline bool operator<(node u) const {return a < u.a;}
} a[N];int T, n, cse;
vector<node> seq;int main() {T = qr();while (T--) {n = qr(), seq.clear();for (int i = 1; i <= n; ++i)a[i].a = qr(), a[i].x = qr();sort(a + 1, a + 1 + n);for (int i = 1; i <= n; ++i) {if (seq.empty() || seq.back().a < a[i].a)seq.push_back(a[i]);else seq.back().x += a[i].x;while (seq.back().x > 2 && (i == n || seq.back().a < a[i + 1].a)) {if (seq.back().x & 1) {int x = (seq.back().x - 1) >> 1;seq.back().x = 1;seq.push_back({x, seq.back().a + 1});} else {int x = (seq.back().x - 2) >> 1;seq.back().x = 2;seq.push_back({x, seq.back().a + 1});}}}n = seq.size();int ans = 1;for (int i = 0; i <= n - 1; ++i) {int j = i;while (j + 1 < n && seq[j + 1].a == seq[j].a + 1)j++;int res = 0;for (int k = j; k >= i; --k)res = (res * 2 + seq[k].x) % MOD;ans = 1ll * ans * (res + 1) % MOD;i = j;}printf("Case #%d: %d\n", ++cse, ans);}return 0;
}