Expected Nonsense Index

Before the band f goes on tour, its members relax by going on a dice travel. In a dice travel there are \(N\) locations numbered \(1,2,\cdots,N\). Initially, all members gather at a starting location \(s_0\). Then they perform \(T\) dice tosses. When at location \(i\), the next destination is chosen uniformly at random among \(m_i\) distinct candidates: \(l_{i,1},l_{i,2},\dots,l_{i,m_i}\). In other words, if the current location is \(s_t\), the next destination \(s_{t+1}\) is chosen uniformly among the candidate list for \(s_t\). The travel ends at \(s_T\) after the \(T\)th toss.

Every time the members arrive at a location \(s_t\) (for \(t\ge 1\)), they enjoy the scenery. However, if the location has been visited before (that is, if there exists a \(t' < t\) with \(s_{t'} = s_t\)), then before tossing the dice at \(s_t\) (or if \(t=T\), without another toss), the dice roller S will say:

[ \text{"Last time we came to } s_t \text{ was at time } t'\text{, and then we rolled } s_{t'+1}.\text{ Who knows what this time will give?}" ]

At that moment, the drummer Y writes down the value \(s_{t'+1}\). The final nonsense index is the sum of all numbers recorded by Y. S is curious about the expected value of this index. It can be shown by linearity of expectation that the final answer is

[ E = \sum_{t=0}^{T-1} \sum_{i=1}^{N} \Bigl(P(\text{dice toss at time } t \text{ gives } i) \cdot i \cdot F(i,i,T-t-1)\Bigr), ]

where for any target location \(i\), \(F(i,j,r)\) is defined recursively for \(r\ge 0\) by:

[ F(i,j,0)=0, \quad F(i,j,r)=\sum_{k\in \text{transitions from } j}\frac{1}{m_j}\Bigl[\mathbf{1}{{k=i}}+\mathbf{1}{{k\neq i}}F(i,k,r-1)\Bigr]. ]

Given the travel configuration and the process described, compute the expected nonsense index.

inputFormat

The input consists of several lines:

1. The first line contains two integers \(N\) and \(T\) (the number of locations and the number of dice tosses).
2. The second line contains an integer \(s_0\) (the starting location).
3. Then follow \(N\) lines. The \(i\)th of these lines describes the transitions from location \(i\). It begins with an integer \(m_i\) (the number of candidate destinations from \(i\)), followed by \(m_i\) distinct integers: \(l_{i,1}, l_{i,2}, \dots, l_{i,m_i}\).

outputFormat

Output a single real number: the expected value of the nonsense index. The answer will be accepted if its absolute or relative error does not exceed \(10^{-6}\).

sample

2 2
1
2 1 2
1 1

1.75