Passwords are widely used in our lives: for ATMs, online forum logins, mobile device unlock and door access. Everyone cares about password security. However, attackers always find ways to steal our passwords. Here is one possible situation:

Assume that Eve, the attacker, wants to steal a password from the victim Alice. Eve cleans up the keyboard beforehand. After Alice types the password and leaves, Eve collects the fingerprints on the keyboard. Now she knows which keys are used in the password. However, Eve won't know how many times each key has been pressed or the order of the keystroke sequence.

To simplify the problem, let's assume that Eve finds Alice's fingerprints only occurs on **M** keys. And she knows, by another method, that Alice's password contains **N** characters. Furthermore, every keystroke on the keyboard only generates a single, unique character. Also, Alice won't press other irrelevant keys like 'left', 'home', 'backspace' and etc.

Here's an example. Assume that Eve finds Alice's fingerprints on **M**=3 key '3', '7' and '5', and she knows that Alice's password is **N**=4-digit in length. So all the following passwords are possible: 3577, 3557, 7353 and 5735. (And, in fact, there are 32 more possible passwords.)

However, these passwords are not possible:

1357 // There is no fingerprint on key '1' 3355 // There is fingerprint on key '7', so '7' must occur at least once. 357 // Eve knows the password must be a 4-digit number.

With the information, please count that how many possible passwords satisfy the statements above. Since the result could be large, please output the answer modulo 1000000007(10^{9}+7).

The first line of the input gives the number of test cases, **T**.

For the next **T** lines, each contains two space-separated numbers **M** and **N**, indicating a test case.

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the total number of possible passwords modulo 1000000007(10^{9}+7).

Time limit: 30 seconds per test set.

Memory limit: 1GB.

**T** = 15.

1 ≤ **M** ≤ **N** ≤ 7.

**T** = 100.

1 ≤ **M** ≤ **N** ≤ 100.

Sample Input

4 1 1 3 4 5 5 15 15

Sample Output

Case #1: 1 Case #2: 36 Case #3: 120 Case #4: 674358851

At new years party there is a pyramidal arrangement of glasses for wine. For example, at the top level, there would just be one glass, at the second level there would be three, then 6 and then 10 and so on and so forth like the following image:

The glasses are numbered using 2 numbers, **L** and **N**. **L** represents the level of the glass and **N** represents the number in that level. Numbers in a given level are as follows:

Level 1: 1 Level 2: 1 2 3 Level 3: 1 2 3 4 5 6 Level 4: 1 2 3 4 5 6 7 8 9 10Each glass can hold

As wine is poured in the glasses, once a glass gets full, it overflows equally into the 3 glasses on the next level below it and touching it, without any wine being spilled outside. It doesn't overflow to the glasses on the same level beside it. It also doesn't overflow to the any level below next level (directly).

For example: When the glass of

Once that the bartender is done pouring

The first line of the input gives the number of test cases, **T**. **T** test cases follow. Each test case consists of three integers, **B**, **L**, **N**, **B** is the number of bottles the bartender pours and **L** is the glass level in the pyramid and **N** is the number of the glass in that level.

For each test case, output one line containing "Case #x: y", where **x** is the test case number (starting from 1) and **y** is the quantity of wine in ml in that glass.

We recommend outputting y to 7 decimal places, but it is not required. y will be considered correct if it is close enough to the correct number: within an absolute or relative error of 10^{-6}.
See the FAQ for an explanation of what that means, and what formats of real numbers we accept.

Time limit: 30 seconds per test set.

Memory limit: 1GB.

1 ≤ **T** ≤ 150.

1 ≤ **B** ≤ 1000.

1 ≤ **L** ≤ 100.

1 ≤ **N** ≤ Number of glasses on the corresponding level.

1 ≤ **B** ≤ 50000.

1 ≤ **L** ≤ 400.

1 ≤ **N** ≤ Number of glasses on the corresponding level.

Sample Input

7 1 2 1 1 1 1 2 1 1 20 1 1 1 3 1 2 3 1 10 4 10

Sample Output

Case #1: 166.6666667 Case #2: 250.0000000 Case #3: 250.0000000 Case #4: 250.0000000 Case #5: 0.0000000 Case #6: 55.5555556 Case #7: 157.4074074

Bob is fond of playing cards. On his birthday party, his best friend Alice gave him a set of cards.

There are **N** cards and each card contains an integer number. He put the cards from left to right on a desk and wants to discard some of them. Before he discards any cards, he will choose a number **K**. At each time, he always chooses 3 **adjacent** cards to discard, and we assume that the numbers on each card from left to right are **a**, **b** and **c**. Bob guarantees that

c - b = b - a = K

Bob want to know what is the smallest number of cards he can be left with at the end. If he ever has a choice of which cards to discard, he chooses the cards and will leave the fewest cards at the end.

The first line of the input gives the number of test cases, **T**. **T** test cases follow.

Each test cases contains two lines. The first line of each test case contains two integers: the number of cards **N** and the number **K** Bob chooses. The second line contains **N** integers **a _{1}**,

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the smallest number of cards Bob can be left with after he has discarded everything he can.

Time limit: 30 seconds per test set.

Memory limit: 1GB.

1 ≤ **T** ≤ 100.

1 ≤ **a _{i}** ≤ 10

1 ≤

**K** = 0.

1 ≤ **K** ≤ 10^{6}.

Sample Input

2 6 0 4 4 3 3 3 4 5 1 3 1 2 3 4

Sample Output

Case #1: 0 Case #2: 2

An **n** parentheses sequence consists of **n** `(`

s and **n** `)`

s.

A valid parentheses sequence is defined as the following:

*You can find a way to repeat erasing adjacent pair of parentheses () until it becomes empty.*

For example,

`(())`

is a valid parentheses, you can erase the pair on the 2nd and 3rd position and it becomes `()`

then you can make it empty.`)()(`

is not a valid parentheses, after you erase the pair on the 2nd and 3rd position, it becomes `)(`

and you cannot erase any more.Now, we have all valid

For example, here are all valid 3 parentheses sequences in lexicographical order:

((())) (()()) (())() ()(()) ()()()

The first line of the input gives the number of test cases, **T**. **T** lines follow. Each line represents a test case consisting of 2 integers, **n** and **k**.

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the **k**-th smallest parentheses sequence in all valid **n** parentheses sequences. Output "Doesn't Exist!" when there are less than **k** different **n** parentheses sequences.

Time limit: 30 seconds per test set.

Memory limit: 1GB.

1 ≤ **T** ≤ 100.

1 ≤ **n** ≤ 10.

1 ≤ **k** ≤ 100000.

1 ≤ **n** ≤ 100.

1 ≤ **k** ≤ 10^{18}.

Sample Input

3 2 2 3 4 3 6

Sample Output

Case #1: ()() Case #2: ()(()) Case #3: Doesn't Exist!

For small dataset, a simple brute-force algorithm will do. Also, since M < 10 and N ≤ 7, you can simply use 32-bit integer to enumerate all potential passwords. Pseudo-code:

```
answer = 0
for password in (0 .. 10
```^{N}-1):
condition1 = every digit in password < M
condition2 = every element in {0 .. M-1} occurs at least once in password
if condition1 == true and condition2 == true:
answer = answer + 1
print(answer)

However, the algorithm above is not fast enough for large dataset. Assume that f(M,N) be the answer. If we ignore the condition that "All M characters should occurs in the password at least once", then the answer will be very simple -- M^{N}.

But we can't ignore that. f(M,N) = M^{N} takes some invalid passwords into count. What are they? They're the passwords formed with less than M characters. More precisely, we need to deduct all f(i,N) from M^{N} where 1≤i<M. Is that enough?

Not yet. Note that we need to choose a set of i characters first. Consider character set S={3,5,7} with N=4. If we want to remove all i=1-character passwords, we need to remove 3333, 5555 and 7777 -- we need to pick up a subset of S with i elements. That's a classical combinatorial problem.

By putting everything together, we have f(M,N) = M^{N} - sigma(1≤i<M)C(M,i)*f(i,N) and f(1,N) = 1. We can easily solve it by using dynamic programming.

Test Data

We recommend that you practice debugging solutions without looking at the test data.

Test Data

We recommend that you practice debugging solutions without looking at the test data.

For small dataset, there is a greedy solution - we can choose any 3 adjacent cards with same number, util we can't find such triple.

For large dataset, there it's a dynamic programming problem. We can define a state **DP[i][j]**, which indicates the smallest number of card Bob can not drop if we consider all cards with index from **i** to **j**. So for every legal state, we have four choices:

- Get rid of the card with index
**i** - Get rid of the card with index
**j** - Choose a card with index
**k**, which meetsa

_{j}- a_{k}= a_{k}- a_{i}= K - Choose a card with index
**k**, and split the cards into two parts(one from**i**to**k**and the other one from**k + 1**to**j**)

Test Data

We recommend that you practice debugging solutions without looking at the test data.

Test Data

We recommend that you practice debugging solutions without looking at the test data.