Expected Unstable Pairs

You are given an application with a total of \(N\) females and \(N\) males, each numbered uniquely from 1 to \(N\). Each female has a subset (possibly empty) of the male numbers as her "preferred list". For a female with a non‐empty list \(L\) (with \(|L| = k\)) sorted in increasing order, the app shows the members of \(L\) cyclically. Every time a male is shown, she accepts him independently with probability \(P\) and rejects him with probability \(1-P\). This process is repeated cyclically over her list until she accepts one of the males. Hence, the probability that she eventually accepts the \(i\)th male (i.e. the one with the \(i\)th smallest number in her list) is given by

\(\displaystyle \Pr[\text{accept } L_i] = \frac{(1-P)^{i-1}P}{1-(1-P)^k}\)

Note that a female with an empty list will not choose any male and is not considered in further analysis.

Now, consider any two different females \(a\) and \(b\) (both having non-empty lists) with indices \(a<b\). If the chosen male for female \(a\) has a number greater than the chosen male for female \(b\), the pair \((a, b)\) is considered an unstable pair.

Your task is to calculate the expected number of unstable pairs over all pairs of females with non-empty lists.

inputFormat

The input is given as follows:

• The first line contains two numbers: an integer \(N\) (the number of females and the number of males) and a real number \(P\) (the acceptance probability).
• Then \(N\) lines follow, one for each female (from female 1 to female \(N\)). Each line begins with an integer \(k\) (the size of her preferred list). If \(k > 0\), it is followed by \(k\) distinct integers representing the male numbers in her preferred list. These numbers are not necessarily sorted, so you may need to sort them in increasing order.

outputFormat

Output a single real number which is the expected number of unstable pairs. Your answer will be accepted if it has an absolute or relative error of at most \(10^{-6}\).

sample

3 1.0
2 1 2
2 1 3
2 2 3

0.0