## 1) Concise abridged problem statement

Given \(N\) married couples, a magician randomly matches each of the \(N\) men to a distinct woman (uniformly among all \(N!\) perfect matchings). Compute the probability that **exactly \(K\)** men are matched with their true wives.  
Output `0` if the probability is zero; otherwise output it as an **irreducible fraction** `A/B`.

Constraints: \(1 \le N \le 100\), \(0 \le K \le N\).

---

## 2) Detailed editorial (solution idea and proof)

### Model as a permutation
Fix an ordering of men and women so that the true matching is:
\[
1 \leftrightarrow 1,\; 2 \leftrightarrow 2,\; \dots,\; N \leftrightarrow N
\]
Any guessed matching is a bijection from men to women, i.e. a permutation \(\pi\) of \(\{1,\dots,N\}\), where man \(i\) is matched to woman \(\pi(i)\).

“Man \(i\) matched to his true wife” means \(\pi(i)=i\), i.e. a **fixed point** of the permutation.

So the problem becomes:

> Pick a uniform random permutation of size \(N\). What is the probability it has exactly \(K\) fixed points?

### Count permutations with exactly \(K\) fixed points
1. Choose which \(K\) positions are fixed points: \(\binom{N}{K}\).
2. On the remaining \(N-K\) positions, we need a permutation with **no fixed points** (a *derangement*). Let \(D_m\) be the number of derangements of \(m\) elements.

Thus the number of permutations with exactly \(K\) fixed points is:
\[
\binom{N}{K}\, D_{N-K}
\]

Total permutations: \(N!\). Therefore:
\[
P = \frac{\binom{N}{K}\, D_{N-K}}{N!}
\]

### Simplify the fraction
Use \(\binom{N}{K} = \dfrac{N!}{K!(N-K)!}\):
\[
P = \frac{ \frac{N!}{K!(N-K)!} \, D_{N-K} }{N!}
= \frac{D_{N-K}}{K!(N-K)!}
\]

So we only need:
- \(m = N-K\)
- \(D_m\)
- denominator \(K!\cdot m!\)

### Computing derangements \(D_m\)
Use the classic recurrence:
- \(D_0 = 1\)
- \(D_1 = 0\)
- \(D_m = (m-1)\bigl(D_{m-1}+D_{m-2}\bigr)\) for \(m \ge 2\)

This is fast for \(m \le 100\) and exact with big integers (Python supports them natively; C++ can use big integer libraries, but in this task the provided solution is Python).

### Output formatting
- If numerator \(D_m = 0\), print `0` (this happens for \(m=1\), i.e. \(K=N-1\)).
- Otherwise reduce the fraction by \(g=\gcd(\text{num},\text{den})\) and print `num/g` / `den/g`.

### Complexity
- Derangement DP up to 100: \(O(N)\)
- Factorials up to 100: \(O(N)\)
- Big integer arithmetic is trivial at this scale.

---

## 3) Provided solution (same code) with detailed line-by-line comments

```cpp
// NOTE: The provided file is Python, not C++.
// Below is the provided Python solution, rewritten verbatim but with detailed comments.

from math import gcd, factorial


def derangements(m):
    """
    Return D_m = number of derangements of m elements,
    i.e., permutations with no fixed points.

    Uses recurrence:
      D_0 = 1
      D_1 = 0
      D_m = (m-1) * (D_{m-1} + D_{m-2}) for m >= 2
    """
    # Base case: empty permutation has 1 derangement (do nothing)
    if m == 0:
        return 1
    # Base case: for 1 element, the only permutation fixes it, so 0 derangements
    if m == 1:
        return 0

    # d_prev2 holds D_{i-2}, d_prev1 holds D_{i-1} as we iterate i upwards.
    # Initialize with D_0 = 1 and D_1 = 0.
    d_prev2, d_prev1 = 1, 0  # D_0, D_1

    # Compute D_2, D_3, ..., D_m iteratively.
    for i in range(2, m + 1):
        # New D_i = (i-1) * (D_{i-1} + D_{i-2})
        # Then shift the window forward:
        #   old D_{i-1} becomes new D_{i-2}
        #   computed D_i becomes new D_{i-1}
        d_prev2, d_prev1 = d_prev1, (i - 1) * (d_prev1 + d_prev2)

    # After loop, d_prev1 == D_m
    return d_prev1


def main():
    # Read K and N
    k, n = map(int, input().split())

    # Let m = N - K be the number of positions that must be NOT fixed points.
    m = n - k

    # Count derangements on those m positions.
    d = derangements(m)

    # If D_m == 0, then probability is zero (only happens when m == 1).
    if d == 0:
        print(0)
        return

    # From the derivation:
    # Probability = D_{n-k} / (k! * (n-k)!)
    numerator = d
    denominator = factorial(k) * factorial(m)

    # Reduce the fraction to irreducible form by dividing by gcd.
    g = gcd(numerator, denominator)
    numerator //= g
    denominator //= g

    # Print as "A/B"
    print(f"{numerator}/{denominator}")


if __name__ == "__main__":
    main()
```

---

## 4) Python solution (independent, detailed comments)

```python
from math import gcd

def derangements(m: int) -> int:
    """
    Compute D_m = number of derangements of m items.
    Recurrence:
      D_0 = 1
      D_1 = 0
      D_m = (m-1) * (D_{m-1} + D_{m-2})
    """
    if m == 0:
        return 1
    if m == 1:
        return 0

    d0, d1 = 1, 0  # D_0, D_1
    for i in range(2, m + 1):
        d0, d1 = d1, (i - 1) * (d1 + d0)
    return d1

def factorial(n: int) -> int:
    """Compute n! as an integer (n <= 100 here)."""
    res = 1
    for x in range(2, n + 1):
        res *= x
    return res

def main() -> None:
    # Input: K N
    k, n = map(int, input().split())

    # We need exactly K fixed points, so the remaining m = N-K points are not fixed
    m = n - k

    # Count derangements among those m points
    num = derangements(m)

    # If there are no such permutations, probability is 0
    if num == 0:
        print("0")
        return

    # Probability = D_m / (k! * m!)
    den = factorial(k) * factorial(m)

    # Reduce fraction
    g = gcd(num, den)
    num //= g
    den //= g

    print(f"{num}/{den}")

if __name__ == "__main__":
    main()
```

---

## 5) Compressed editorial

Treat a matching as a random permutation of size \(N\); correct couples are fixed points.  
Number of permutations with exactly \(K\) fixed points:
\[
\binom{N}{K} D_{N-K}
\]
so probability:
\[
\frac{\binom{N}{K} D_{N-K}}{N!}=\frac{D_{N-K}}{K!(N-K)!}.
\]
Compute \(D_m\) by \(D_0=1\), \(D_1=0\), \(D_m=(m-1)(D_{m-1}+D_{m-2})\).  
If numerator is 0 print `0`, else reduce by gcd and print `A/B`.