Text for Codesprint 2 Problems

### Picking Cards

There are N cards on the table and each has a number between 0 and N. Let us denote the number on the ith card by ci. You want to pick up all the cards. The ith card can be picked up only if at least ci cards have been picked up before it. (As an example, if a card has a value of 3 on it, you can't pick that card up unless you've already picked up 3 cards previously) In how many ways can all the cards be picked up?
Input:
The first line contains the number of test cases T. T test cases follow. Each case contains an integer N on the first line, followed by integers ci,...,cN on the second line.
Output:
Output T lines one corresponding to each test case containing the required answer for the corresponding test case. As the answers can be very big, output them modulo 1000000007.
Sample Input:
3
3
0 0 0
3
0 0 1
3
0 3 3
Sample Output:
6
4
0
Sample Explanations:
For the first case, the cards can be picked in any order, so there are 3! = 6 ways.
For the second case, the cards can be picked in 4 ways: {1,2,3}, {2,1,3}, {1,3,2}, {2,3,1}.
For the third case, no cards can be picked up after the first one, so there are 0 ways to pick up all cards.
Constraints:
1 <= T <= 10
1 <= N <= 50000
0 <= ci <= N

### Coin Tosses

You have an unbiased coin which you want to keep tossing until you get N consecutive heads. You've tossed the coin M times and surprisingly, all tosses resulted in heads. What is the expected number of additional tosses needed until you get N consecutive heads?
Input:
The first line contains the number of cases T. Each of the next T lines contains two numbers N and M.
Output:
Output T lines containing the answer for the corresponding test case. Print the answer rounded to exactly 2 decimal places.
Sample Input:
4
2 0
2 1
3 3
3 2
Sample Output:
6.00
4.00
0.00
8.00
Sample Explanations:
If N = 2 and M = 0, you need to keep tossing the coin until you get 2 consecutive heads. It is not hard to show that on average, 6 coin tosses are needed.
If N = 2 and M = 1, you need 2 consecutive heads and have already have 1. You need to toss once more no matter what. In that first toss, if you get heads, you are done. Otherwise, you need to start over, as the consecutive counter resets, and you need to keep tossing the coin until you get N=2 consecutive heads. The expected number of coin tosses is thus 1 + (0.5 * 0 + 0.5 * 6) = 4.0

If N = 3 and M = 3, you already have got 3 heads, so you do not need any more tosses.

Constraints:
1 <= T <= 100
1 <= N <= 1000
0 <= M <= N

### Direct Connections

Enter-View (shortly EV) is a linear, street-like country. By linear, we mean all the cities of the country are placed on a single straight line - the axis. Thus every city's position can be defined by a single coordinate, xi, the distance from the left borderline of the country. You can treat all cities as single points.
Unfortunately, the dictator of telecommunication of EV (Mr. S. Treat Jr.) is not an intelligent man. He doesn't know anything about the modern telecom technologies, except for peer-to-peer connections. What's more, his thoughts on peer-to-peer connections is extremely faulty: he believes that, if Pi people are living in city I, there must be at least Pi cables from city i to every other city of EV - this way he can guarantee no congestion will ever occur!
Expectedly, Mr. Treat is not good in math and computing. He hires an engineer to find out how much cable they need to implement this telecommunication system, given the coordination of the cities
and their respective population.
Input:
A number T is given in the first line and then comes T blocks, each representing a scenario.
Each scenario consists of three lines. In the first line a number N is given, which is the number of the cities. Then in the second line, coordination of these N cities come. Finally in the third line, population of the cities comes in the same order.
Output:
For each scenario of the input, write the amount of cable needed in a single line modulo 1,000,000,007.
Sample Input:
2
3
1 3 6
10 20 30
5
5 55 555 55555 555555
3333 333 333 33 35
Sample Output:
280
463055586
Sample Explanation:
For the first test case, having 3 cities requires 3 sets of cable connections. Between city 1 and 2, which has a population of 10 and 20, respectively, Mr. Treat believes at least 10 cables should come out of city 1 for this connection, and at least 20 cables should come out of city 2 for this connection. Thus, the connection between city 1 and city 2 should will require 20 cables, each crossing a distance of 3-1 = 2 km. Applying this absurd logic to connection 2,3 and 1,3, we have
[1,2] => 20 connections x 2 km = 40 km of cable
[2,3] => 30 connections x 3 km = 90 km of cable
[1,3] => 30 connections x 5 km = 150 km of cable
For a total of 280 km of cable
Constraints:
1 ≤ T ≤ 20
1 ≤ N ≤ 200,000
Pi <=10,000
Border to border length of the country <= 1,000,000,000