Moving Stones

Ann and Bob have been experimenting with potential gambling games. Their latest idea starts with B bowls arranged in a circle and S stones distributed among the bowls. The stones are numbered from 1 to S so that they are easily identified. The starting distribution of the S stones among the B bowls can be any one of the possible distributions, provided that the stones are not all placed in a single bowl.

Ann and Bob have an electronic device which, when pressed, will give a random number in the range 1 to S so that a stone can be picked at random. They also have a fair coin which can be flipped to produce Heads or Tails. They define a move as follows:

The device is used to give the number of a stone. The coin is then flipped. If the result is Heads the numbered stone is moved to the neighbouring bowl on the right. If the result is Tails the numbered stone is moved to the neighbouring bowl on the left. Moves continue until all of the stones are in a single bowl. The number of moves needed to achieve this is counted. The gambling game requires players to guess this number of moves before any moves have been made. The player with the closest guess wins.

Clearly a player has a marked advantage if they can calculate the expectation number of moves before the game starts (although this does not necessarily guarantee that they will win). This problem requires you to calculate the expectation number of moves.

Let us consider a fairly small game with 4 bowls and 5 stones (so B = 4 and S = 5). This is small enough for you to experiment with a simulation, although a simulation is unlikely to give you sufficient accuracy to solve the problem. Let the initial distribution of the stones in the 4 bowls be 2, 0, 2 and 1. However, since the stones are all distinguishable it is more helpful to show the stone numbers. We can represent the stones in the 4 bowls as follows:

 (1,2)     ( )     (3,4)     (5)

In the first move we will select one of the 5 stones to move and then move it by one bowl, either to the right or left. This means that there are 10 possible moves. The resulting distributions after making each of these moves are shown in the list below.

  (2)      (1)     (3,4)     (5)
  (2)      ( )     (3,4)    (1,5)
  (1)      (2)     (3,4)     (5)
  (1)      ( )     (3,4)    (2,5)
 (1,2)     ( )      (4)     (3,5)
 (1,2)     (3)      (4)      (5)
 (1,2)     ( )      (3)     (4,5)
 (1,2)     (4)      (3)      (5)
(1,2,5)    ( )     (3,4)     ( )
 (1,2)     ( )    (3,4,5)    ( )

The first example shows that stone 1 has been picked and has been moved by one bowl to the right. The second example also has stone 1 picked, but moved by one bowl to the left (Remember that the bowls are arranged in a circle).

With this example and the given initial distribution, we can calculate that the expectation number of moves to complete the game is 291.66666666666. You are asked to give answers in scientific notation, rounded to 10 digits after the decimal point. The answer to this example would be given as 2.9166666667e+02 (Note the 2-digit exponent).

Input/Output description: The first line of the input data will contain two integers B and S, separated by a space. The second line will contain B space-separated integers, giving the initial distribution of the S stones in the B bowls. Find the expectation number of moves to reach a distribution where all of the stones are in a single bowl. Give your answer in scientific notation using the format described above.

Example 1:

input:
4 5
2 0 2 1

answer:
2.9166666667e+02

Example 2:

input:
12 6
0 1 0 2 0 0 3 0 0 0 0 0 

answer:
2.7887689108e+05