407531: GYM102822 L Lottery

Little Rabbit walks into a shopping mall and comes across a lottery activity. There are $$$n$$$ boxes. Inside the $$$i$$$-th box, there are $$$x_i$$$ balls labeled with $$$2^{a_i}$$$. 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 $$$10^9+7$$$.

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

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

Then in the next $$$n$$$ lines, the $$$i$$$-th line contains two integers $$$a_i$$$ ($$$0 \le a_i \le 10^9$$$) and $$$x_i$$$ ($$$1 \le x_i \le 10^9$$$), which means there are $$$x_i$$$ balls numbered $$$2^{a_i}$$$ inside the $$$i$$$-th box. It's guaranteed that $$$a_1,a_2,\dots,a_n$$$ are all distinct.

For the $$$x$$$-th test case, if the answer modulo $$$10^9+7$$$ is $$$y$$$, output $$$Case$$$ #$$$x$$$: $$$y$$$ in a single line.

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

Case #1: 8
Case #2: 18