Hide

Problem DSeven Up

The one-player game of Seven Up is played with a standard deck of 52 cards - each card has one of thirteen possible faces which we denote by A, 2, 3, 4, 5, 6, 7, 8, 9, T, J, Q, and K. There are exactly four cards of each face.

Initially, seven cards are dealt face down in positions numbered 1 through 7. The ace (A) has value $1$, the cards with faces 27 have corresponding values $2$ through $7$, and the remaining cards do not have any value.

A single turn consists of the player drawing a card from the top of the deck (initially having $52-7 = 45$ cards). The following steps are repeated until the turn is ended:

• if the card has no value (i.e. the face is not one of A, 2, 3, 4, 5, 6, or 7), the turn has ended,

• otherwise if the card in the position corresponding to the value of the card held by the player is already face up, the turn has ended,

• otherwise the player swaps the card they are holding with the card in the corresponding position except the card they placed in this position is now face up, the current turn continues

At the end of a turn, if all seven positions have a face-up card, the game ends.

If the remaining $45$ cards are randomly permuted so each ordering is equally likely, what is the expected number of turns until the game completes?

More specifically, if for any $1 \leq k \leq 45$ we let $p_ k$ denote the probability (over the random ordering of the remaining $45$ cards) the game finishes after $k$ turns are completed. You should compute $\sum _{k = 1}^{45} k \cdot p_ k$.

Input

Input consists of a single string consisting of exactly 7 characters from A23456789TJQK denoting the faces of the 7 cards that were dealt face down into their corresponding positions. No face will appear more than four times in this string.

Output

Output a single value giving the expected number of turns until the game completes. Your answer should have an absolute or relative error of less than $10^{-6}$.

Sample Input 1 Sample Output 1
A9Q22T5

19.88129713423831

Sample Input 2 Sample Output 2
JQQQKKK

20.91314505643106

Hide