What about final participants. We are waiting!

For every edge in the path, calculate the expected number of moves until you use that edge in that direction. The answer is the sum of these numbers. To calculate these numbers, it's just the expected number of times you pass through the vertex * expected number of moves until getting back to it + 1 or something like this. http://codeforces.me/problemset/problem/712/E it's similar to this problem. You can calculate the expected number to the up edges using one dfs and then the rest in another, then just use binary lifting to calculate the path. We just passed it like this but during the contest we had no time to code binary lifting :(

D: 2^{2(n - 1)(n + 1)} due to some combinatorical reasons.

My solution used precalc for all possible n with O(n^4) complexity.

How to solve it for fixed n:

Let's notice that we have got 209 single days and 52 groups with 3 days which all turn to Monday (Sat, Sun, Mon).

Let's calculate dp[i] — probability that exactly i persons were born on this 209 single days (we can do it easily with O(n^2)).

So, we have gotten this probabilities. Then we need to calculate the expected value for every i and we will have solved the problem.

Let's fix i. Let's solve(a, b) — expected value for a days and b persons which were born all on those a days. So for every i we need to calculate solve(209, i) + solve(52, n-i) and multiply this with dp[i].

We can calculate solve(a, b) with dp[i][j] — probability of the event where we have taken men so that on exactly i days several men were born, on exactly j days only 1 man was born. So we will recalculate this step by step, adding men. Answer eventually will be (sum i*dp[i][j]) for all (i, j). Total complexity of this dp is O(n^3), of solution O(n^4).

There is simply solution from participants. ANS = 52 * p₁ + 209 * p₂

p₁, p₂ — probability that there will be at least 2 people that were born in concrete 3 days / day, p₁ for mondays and weekends, p₂ about other days.