Your friend baked \(N\) batches of cookies, the first with chocolate chips, and the rest with raisins. Batch \(i\) has \(C_i\) cookies all having the same weight \(W_i\). Cookies in different batches may have the same weight. Initially, all cookies are scattered on the table, and you hope to find a hefty one to eat with your trusty balance scale.

First, you select a single cookie uniformly at random from the table and place it on the left side of the scale. Then, \(K\) times, you will select a cookie uniformly at random from the table, place it on the empty side of the scale, and throw away the lighter of the two cookies on the scale (or the cookie on the left side if they both weigh the same).

{{PHOTO_ID:502174485028685|WIDTH:700}}

Determine the probability that after throwing away \(K\) cookies, the remaining cookie on the scale is a yummy chocolate chip cookie from batch \(1\).

If we write this probability as a quotient of integers \(p/q\) in lowest terms, then you should output this quotient modulo \(1{,}000{,}000{,}007\) — in other words, output the unique integer \(x\) such that \(0 \le x \lt 1{,}000{,}000{,}007\) and \(p = (x * q) \text{ mod } 1{,}000{,}000{,}007\).

# Constraints

\(1 \le T \le 1{,}000\)
\(2 \le N \le 3{,}000\)
\(1 \le K \lt \sum_{i=1}^{N} C_i\)
\(1 \le C_i \le 3{,}000\)
\(1 \le W_i \le 10^{9}\)

# Input Format

Input begins with a single integer \(T\), the number of test cases. For each test case, there is first a line containing two-space separated integers \(N\) and \(K\). Then, \(N\) lines follow, the \(i\)th of which contains two space-separated integers \(C_i\) and \(W_i\).

# Output Format

For the \(i\)th test case, output a single line containing `"Case #i: "` followed by the unique integer \(x\) such that \(p = (x * q) \text{ mod } 1{,}000{,}000{,}007\).

# Sample Explanation

In the first case, there are \(5\) batches with \(1\) cookie each. Since we only weigh \(K=1\) time, the only way for the last cookie to be chocolate chip is if it's one of the two placed on the scale. There's a \(\frac{1}{5}\) chance of picking it for the initial cookie, and a \(\frac{4}{5}\cdot\frac{1}{4}\) chance of picking it for the second cookie. In either case, because it's the heaviest, it will remain on the scale. Adding these independent events' probabilities, we get a \(\frac{1}{5} + \frac{4}{5}\cdot\frac{1}{4} = \frac{2}{5}\) chance that the last cookie on the scale is chocolate chip. Here, we print \(800{,}000{,}006\) since \(2 = (800{,}000{,}006 * 5) \text{ mod } 1{,}000{,}000{,}007\).

The second case is the same, except we must weigh a second time. There's a \(\frac{2}{5}\) chance of picking chocolate chip the first or second times, and a \(\frac{3}{5}\cdot\frac{1}{3}\) chance of picking it the third time. The answer is \(\frac{2}{5} + \frac{3}{5}\cdot\frac{1}{3} = \frac{3}{5}\). We print \(200{,}000{,}002\) since \(3 = (200{,}000{,}002 * 5) \text{ mod } 1{,}000{,}000{,}007\).

In the third case, there are \(2\) batches of \(10\) cookies each, where batch \(2\) cookies are heavier. Since we must weigh and throw out \(10\) cookies, we must have weighed a cookie from batch \(2\) at least once, after which a batch \(1\) cookie can never remain on the scale. Therefore the answer is \(0\).

In the fourth case, there is a \(\frac{5}{24}\) chance that the final cookie on the scale is chocolate chip.