Dolphins
Spring… Rabbits are happy to see sun, sky is nice and soft, flowers are blooming. Dolphins returned back from warm counties.
Really, dolphins for rabbits are symbols of spring. They sing so nice, fly so nice, twirl so nice. This behavior amuses everyone. Almost… Rabbits-scientists from the Institute of dolphin population in trees tops management of the Rabbitland get a lot of work these sunny times. They need to manage big flocks of dolphins. But they hope that we will design for them an algorithm to forecast dolphin population in trees tops.
Thus, we need to write a program which will find probably positions of dolphins. First it will get description of N dolphins, sitting at M trees. Every dolphin initially sits at top of some tree. Every dolphin in one second with same probability can fly to any tree with number which is prime to the number of tree where is used to sit (relatively prime integers have GCD equal to 1), or stay at the same tree. In this way, if we have 6 trees, and dolphin is sitting at tree with number 3, then events "dolphin in a second will be at tree with number 1 (or 2, 3, 4, 5)" – are equally possible.
To make sure that your algorithm is correct, you need to output the sum of means of number of dolphins on trees (after T seconds). In other words, if m_1, m_2, ..., m_M – means of number of dolphins on the first, second, …, Mth tree we need to calculate
Input
The first line of the input contains tree integers, separated by spaces: N, M, T (1 ≤ M, N, T ≤ 1000) – number of dolphins, number of trees, time, correspondingly, to be simulated. The second line contains N integers, separated by spaces, which represent positions of dolphins (trees are enumerated from 1 to M).
Output
The only line at the output should have computation results with 2 digits after dot.