Cherry the turtle lives in a long, narrow pond. When cross-sectionally viewed from the side, the floor of the pond can be divided into \(N\) columns, each flat and 1 metre wide. The \(i\)th column from the left is at a depth of \(D_i\) metres below ground level, and all \(N\) column depths are distinct. The pond is surrounded by dirt (at ground level), just to the left of column 1 and the right of column \(N\). Cherry loves to sit on the floor in the leftmost column and bask as much as possible — but only when it's dry. Fortunately for her, the pond is initially devoid of water.

For example, if \(D = [3, 5, 4, 1, 2]\), the pond would look as follows (with Cherry's position indicated in green):

{{PHOTO_ID:311416436611683}}

Unusually enormous drops of rainwater are about to begin falling into the pond, one by one, each onto a random column (drawn uniformly at random from the set of \(N\) columns). Each drop contains 1 cross-sectional square metre of water, and obeys the following process:

1. It falls until it hits a flat *surface*. This surface consists of the highest (least deep) point in its column (which might be either the floor of the pond itself or an existing layer of water atop it), as well as all contiguous equally-deep points to the left and right of it.
2. If that surface is immediately surrounded by any deeper columns to its left and/or right, then the drop's water flows down onto one of them. If there's only one such adjacent deeper column, then the drop flows onto that one. If the columns to the left and right are both deeper than the surface (note that this can only occur if the surface consists of a single column), then the drop's water all flows to the *left* one. Either way, once the drop flows into a different column, the process repeats back from Step 1.
3. Otherwise, the drop's 1 cross-sectional square metre of water spreads itself out evenly across the entire surface it landed on (which will never cause that surface to "overflow" by becoming strictly higher than the columns to its left or right).

Cherry will be forced to stop basking as soon as a non-zero amount of water comes to rest atop column 1. She doesn't mind if raindrops fall directly on column 1 but then immediately flow away from it.

For example, if a raindrop were to fall in column 4 of the above pond, it would flow to the left (onto column 3), and then flow left again to settle in column 2:

{{PHOTO_ID:3533638723394837}}

If a raindrop then fell in column 1, it would flow to the right and spread itself out over the surface spanning columns 2 and 3:

{{PHOTO_ID:299743861289784}}

If a raindrop then fell in column 5, it would remain there:

{{PHOTO_ID:1094784447639382}}

Another raindrop falling in column 5 (or *any* column) would then yield the following state:

{{PHOTO_ID:747829032476688}}

And one more raindrop falling in any column would yield the following state (forcing Cherry to stop basking due to column 1 becoming submerged in water):

{{PHOTO_ID:477696676534167}}

Determine the expected number of drops which will fall before Cherry is forced to stop basking. This will always occur after a finite number of drops have fallen, and before any water overflows the pond.

Let this expected number of drops be represented as a quotient of integers \(p/q\) in lowest terms. Output the value of 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 \equiv x*q\text{ }(\text{modulo }1,000,000,007)\).

# Constraints

\(1 \le T \le 50\)
\(1 \le N \le 30\)
\(1 \le D_i \le 30\)
\(D_{1..N}\) are distinct

The sum of \(N\) across all ponds is at most 1000.

# Input

Input begins with an integer \(T\), the number of ponds. For each pond, there are 2 lines. The first line contains a single integer \(N\). The second line contains the \(N\) space-separated integers \(D_{1..N}\).

# Output

For the \(i\)th pond, print a line containing *"Case #i: "*, followed by a single integer, the expected number of drops which will fall before the leftmost column becomes covered in water, expressed as a quotient of integers modulo 1,000,000,007.

# Explanation of Sample

The first pond initially looks as follows:

{{PHOTO_ID:1173260263089522}}

If the first raindrop falls in column 1, it will settle there, and if it falls in column 2 instead, it will flow into column 1. Either way, Cherry's position will be submerged and she'll be forced to stop basking.

The second pond initially looks as follows:

{{PHOTO_ID:127321889008596}}

The first raindrop will always settle in column 2, leaving Cherry uninterrupted. However, the second raindrop will then always land on the surface spanning both columns, filling both up to a depth of 0.5 metres below ground level and thus forcing Cherry to stop basking.

The third pond only has a single column, and Cherry will need to stop basking as soon as the first raindrop falls in it.

The fourth pond may end up in various states depending on which columns the raindrops fall in. If the first drop falls in either column 1 or 2, then it will immediately settle in column 1, while if it falls in column 3, it will remain there and it will take a second drop to force Cherry to stop basking. The answer is therefore \(\frac{2}{3} 1 + \frac{1}{3} 2 = \frac{4}{3}\). \(4 \equiv 333,333,337 * 3\text{ }(\text{modulo }1,000,000,007)\), meaning that \(333,333,337\) should be outputted.