As Lord Rama's army is approaching Lanka they have to pass one last hurdle and that is the ocean in between. They have decided to construct a bridge made of stones. But before they start constructing it Lord Rama asked Hanuman to train the monkeys in the army.
Hanuman decided to train monkeys with the following strategy.
-
Monkeys stand in a straight line along the x-axis with their faces in the positive y-direction. Each monkey is given a stone.
-
Each monkey throws his stone to either left or right along the line.
-
When two stones traveling with the same speed collide they just reverse their directions and continue to move in the new direction.
-
Each stone travel with the same speed of 1 unit per second. Assume that the radius of stone is zero and can be treated as a point.
Each monkey can decide direction(left or right) for his stone with equal probability. At time t = 0, Hanuman blows his horn and each monkey throws his stone in the chosen direction.To measure their performance Hanuman decided to find the expected number of collisions in a give time T seconds(including the collision at T second).
Help Hanuman to find this value.
Input:
You will be given an integer N denoting the number of monkeys in the line and an integer T denoting the time.
Next line will contain N non-negative integers denoting the position of monkeys.
Output:
Output a single line containing the value Hanuman decided to calculate.
Constraint:
0 < N <= 20
0 < T <= 100000000 (10^8)
0 <= Position of Monkey <= 100000000 (10^8)
