Holiday Travel

Many thanks to Clive Fraser for this puzzle!

In the country of Erehwon there are no large towns. The population is spread over a large number of small villages. The road network is made up of a number of link roads. Each link road is a direct connection between neighbouring villages and does not pass through any other village on the way. There is a unique route, using the network of link roads, between every two villages in the country. Because of economies in the road building programme, there is only one possible route between any two villages.

Erehwon is a popular tourist destination, so many of the villages have a hotel to provide the necessary accommodation. No village has more than one hotel. Ann and Bob do a great deal of travelling to a variety of different countries. They are often in contact to find out which is the latest exotic location to be visited by their friend. On the most recent contact, Ann and Bob were surprised to find that they were both visiting Erehwon at the same time. As Bob had a hire car, he suggested that they should meet up but wondered how far he would need to drive to meet Ann.

This problem requires you to work out the expectation distance that Bob will have to drive, assuming that both Ann and Bob have chosen their hotels purely at random.

There are N villages in Erehwon. All of these have delightful names but, for the purpose of the problem, we will refer to them using the numbers 0 to N-1. There is a hotel at village 0. You now need to have information about each of the other N-1 villages. There is a great deal of this so we will use the Linear Congruential Generator to generate the data. This has been used before in Code Abbey problems. A random value X(n) is generated using the formula:

X(n) = (A * X(n-1) + C) % M

In this problem we will use the values A = 445, C = 700001 and M = 2097169. Note that % M means the remainder after dividing by the modulus value of M. The value X(n-1) is the previous random value to be generated by this expression. In order to generate the first random value X(1) we need to be given a value for X(0) which is called the seed for the generator. This value will be supplied as part of the data for the problem. The random values X(n) are too large to be used directly, so we will use the following rules to derive our data from the value X(n). For each village number V, where V ranges from 1 to N-1, the value of X(n) is used to provide three separate pieces of data, as described below.

If X(n) is odd, village V has a hotel.
There is a link road from village V to village W, where W = X(n) % V.
The length of this link road is L, where L = 10 + X(n) % 100.

Consider a simple example where N = 8 and the random seed X(0) = 1234. We need to generate 7 random values for each of the villages from V = 1 to V = 7. The first 7 random values generated are: 1249131, 813511, 1999328, 1201305, 502631, 2070882, 1585300.

For village V = 1 we have X(n) = 1249131. This is an odd number so village 1 has a hotel. X(n)%V = 1249131%1 = 0, so there is a link road connecting village 1 to village 0. 10 + X(n)%100 = 10 + 31 = 41, so the length of the link road is 41. In a similar way we can determine the following results for villages 2 to 7.

Village 2 has a hotel and is connected to village 1 by a road of length 21.
Village 3 does not have a hotel and is connected to village 2 by a road of length 38.
Village 4 has a hotel and is connected to village 1 by a road of length 15.
Village 5 has a hotel and is connected to village 1 by a road of length 41.
Village 6 does not have a hotel and is connected to village 0 by a road of length 92.
Village 7 does not have a hotel and is connected to village 3 by a road of length 10.

In this example there are 5 hotels in Erehwon. These are located in villages 0, 1, 2, 4 and 5. Ann and Bob can be staying at any one of them, so there are 25 possibilities. These are listed below, together with the distance between the hotels in each case.

Ann Bob Distance
0   0   0
0   1   41
0   2   62
0   4   56
0   5   82
1   0   41
1   1   0
1   2   21
1   4   15
1   5   41
2   0   62
2   1   21
2   2   0
2   4   36
2   5   62
4   0   56
4   1   15
4   2   36
4   4   0
4   5   56
5   0   82
5   1   41
5   2   62
5   4   56
5   5   0

The sum of these 25 distances is 944 so the average distance and hence the required expectation value is 37.76. This result has been used for example 1 below. Example 2 has a larger number of villages (N = 500) but is still small enough to provide useful test data. The actual problem will have N = 400000.

Input/Output description: The first and only line of the input data will contain 2 space separated integers. These are the random seed X(0) and the problem size N. You need to determine the Expectation Distance between Ann and Bob. Give your answer rounded to 6 decimal places.

Example 1:

input:
1234 8

answer:
37.760000

Example 2:

input:
12345 500

answer:
541.651914

Example 3:

input:
123456 400000

answer:
1414.587177