== include(page="template/taskheader" task_id="swaps") ==

$Domnul B.$ este un artist modern. Ultima sa mare creatie este, intr-o forma extrem de stilizata, permutarea identica de lungime $N$ (adica permutarea $1, 2, 3 ... N$).

Definim functia $f(N, P, A, B)$ ca fiind probabilitatea ca numarul $A$ sa ajunga pe pozitia $B$ dupa efectuarea a $P$ interschimbari aleatoare de cate doua numere asupra permutarii identice de lungime $N$. De exemplu, $f(3, 1, 1, 2)$ este egal cu $0.(2)$, deoarece avem $9$ posibilitati de alegere a pozitiilor interschimbate, $(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)$, dintre care doar doua produc rezultatul dorit $((1, 2)$ si $(2, 1))$.

$Domnul C.$ este malitios. Ultimul sau mare plan este de a distruge ultima mare creatie a $Domnului B.$, facand interschimbari aleatoare ale unor numere din permutare. Mai exact, la un pas, $Domnul C.$ isi va alege cu probabilitate egala doua pozitii, $i$ si $j$ si va interschimba continutul celor doua pozitii din permutare.
$Domnul C.$ are in cap $T$ intrebari, iar in functie de raspunsurile voastre isi va alege cea mai malitioasa strategie pentru a distruge creatia $Domnului B.$ O intrebare are forma urmatoare: $P A B$, cu semnificatia "Care este probabilitatea ca dupa $P$ pasi, numarul $A$ sa ajunga pe pozitia $B$?"
 
Ajutati-l pe $Domnul C.$, raspunzand corect la fiecare dintre cele $T$ intrebari.

Dandu-se $T$ teste de forma $N P A B$, sa se calculeze pentru fiecare dintre acestea $f(N, P, A, B)$.

h2. Date de intrare

Fişierul de intrare $swaps.in$ va contine pe prima linie numerele naturale $N$ si $T$. Urmatoarele $T$ linii vor contine triplete de forma $P A B$, cu semnificatia din enunt.

Fişierul de intrare $swaps.in$ va contine pe prima linie numarul natural $T$. Urmatoarele $T$ linii vor fi de forma $N P A B$, cu semnificatia din enunt.

h2. Date de ieşire

h2. Restricţii

* $1 ≤ N ≤ 10.000$

* $1 ≤ N ≤ 1.000.000$

* $1 ≤ A, B ≤ N$

* $1 ≤ P ≤ 1.000.000.000$

* $1 ≤ P ≤ 1.000.000$

* $1 ≤ T ≤ 100.000$

* Rezultatele se vor afisa cu o precizie de $10^-6^$

* Rezultatele se vor afisa cu o precizie de $10^-9^$

* $A$ si $B$ pot sa fie si egale.
* In cazul in care pozitiile alese pentru interschimbare sunt identice, permutarea va ramane la fel pentru pasul urmator.

* Pentru 20% din teste, $T ≤ 20, N ≤ 100$ si $P ≤ 100$.
* Pentru alte 20% din teste, $T ≤ 20 si P ≤ 100.000$.

h2. Exemplu
table(example). |_. swaps.in |_. swaps.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3
6 3 1 4
6 4 1 1
3 3 2 3
| 0.117283951
0.331275720
0.320987654

|

h3. Explicaţie
 
...
 
== include(page="template/taskfooter" task_id="swaps") ==
 

== include(page="template/taskfooter" task_id="swaps") ==

7311