eolymp
bolt
Try our new interface for solving problems
Problems

Probablisctic OR

Probablisctic OR

Time limit 1 second
Memory limit 64 MiB

Everyone knows OR operation. Let us define new operation which we will call Probablistic OR. We will denote this operation as #. For given real number p (0p1) and two bits a and b:

  • if a = 1 and b = 1, then #(a, b) = 1;

  • if a = 0 and b = 0, then #(a, b) = 0;

  • else #(a, b) = 0 with probability p, #(a, b) = 1 with probability 1-p.

Now for two given non-negative integers x and y we can define bitwise Probablistic OR operation. The result of this operation is a number received by performing # operation for each pair of bits of x and y in same positions. For example, for p = 0.5, x = 2, and y = 4, we will get 0, 2, 4 or 6 each with probability 0.25.

You will be given a list of non-negative integers. You have to implement a program which will calculate the expected value of the result of performing bitwise probablistic OR operation on all these numbers given some p. The numbers will be taken from left to right.

Input data

Input file starts with real number p (0p1) with exactly two digits after the decimal point. Integer n follows (1n100). Next line contains n numbers ai in the order they are taking part in the operation (0a_i10^9).

Output data

Output the expected value of performing Probablistic OR operation on the given numbers for given p. Print the result with two digits after the decimal point.

Examples

Input example #1
0.25 4
1 2 3 4
Output example #1
5.11
Source International Collegiate Programming Contest, Ukraine, Quarter-Final,May 19, 2011