Dinner Bet

Time limit2sMemory limit512 MB

Summary

Given N balls, D drawn per round, and two size-C cards, find the expected number of rounds until one player completes their card.

Level: Medium7 of 10
Topics: Probability, Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

Cesar and Raul like betting and good food. They want to try a new fancy restaurant, so they agreed to play a game and let the loser pay for dinner.

A box holds $N$ balls, and each ball carries a distinct number between $1$ and $N$ . The game runs by these rules.

At the start, each person picks $C$ distinct numbers between $1$ and $N$ and writes them on his own card.
In each round, $D$ balls are drawn from the box. Every choice of $D$ balls is equally likely. Cesar and Raul mark the drawn numbers that appear on their own cards. The $D$ balls then go back into the box.
The game stops in the round where a player has marked every number on his card, and that player wins. If both players finish in the same round, the game is a draw and they split the dinner.

You are given the number of balls $N$ , the number of balls drawn each round $D$ , the card size $C$ , and the numbers the two players wrote down. Find the expected number of rounds the game lasts.

Input

The first line contains three space separated integers $N$ , $D$ , and $C$ . The second line contains the $C$ numbers Cesar wrote down, and the third line contains the $C$ numbers Raul wrote down, both space separated. The $C$ numbers on one line are distinct.

Output

Print the expected number of rounds the game lasts on one line, rounded to five digits after the decimal point.

Constraints

$1 \le N \le 50$ : the number of balls in the box
$1 \le D \le \min(10, N)$ : the number of balls drawn each round
$1 \le C \le \min(10, N)$ : the card size
Every number written on a card is between $1$ and $N$ , and the numbers on one card are distinct.

Examples2

Example 1
Input
```
2 1 1
1
2
```
Expected output
```
1.00000
```

Example 2

Input

30 5 10
2 3 5 7 11 13 17 19 23 29
20 18 16 14 12 10 8 6 4 2

Expected output

13.30378