407531: GYM102822 L Lottery

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

L. Lotterytime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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$$$.

Input

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.

Output

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

ExampleInput
2
3
1 1
2 1
3 1
3
1 1
2 2
3 3
Output
Case #1: 8
Case #2: 18

加入题单

上一题 下一题 算法标签: