<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

356. Extrasensory Perception
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



His Royal Highness the King of Berland Berl XV has just decapitated his magician for being politically incorrect. It is a truth universally acknowledged that every king in the possession of a good fortune is in a want of a decent sorcerer. Heralds all over the country have spread the news about the coming Berland-wide wizard competition that is to end up with the announcement of the winner's name. The winner is to join the royal retinue as His Royal Highness' Counselor.

Magician Resool graduated from Bexford University ten years ago and since that time he has been chased by misfortunes and disasters. His wife, an accomplished, still pretty looking lady, believes her husband can do much better than just grumbling about the unfair life. She suggests that he should try his magic powers at the competition and reminds him of his famous trick. The gist of the trick is to see through people's souls.

After two weeks of training Resool makes himself enter the Great Hall of Berland Palace and demonstrate his exceptional abilities. His Royal Highness the King of Berland Berl XV gives him an assignment: N men and N women are presented, and the fact is known that they form N married couples; Resool is to identify a wife for every husband. After the magician casts a spell, burns some magic herbs, and performs ritual dance he still fails to answer correctly. He only manages to guess K married couples out of N. But The King is full of sympathy for the magician and can't just let the magician go away jobless and sorrowful. So, he hires him as a yard-keeper. Now Resool has a lot of free time on his new job and wants to calculate the chances he had at the competition. He wants to know the probability of guessing correctly exactly K married couples when given N men, N women, and a fact that they form N married couples. This will definitely help him during the competition next time.

Input
Input file contains two integers K and N (1 ≤ N ≤ 100; 0 ≤ K ≤ N) separated by a space.

Output
Print the required probability to the output file. If the answer is zero, simply print "0" (without quotes). Otherwise print the answer in a form of irreducible fraction "A/B" (without quotes), where A and B are positive integers without leading zeroes. See examples below for the format of output.

Example(s)
sample input
sample output
2 5
1/6

sample input
sample output
9 10
0

<|response|>
## 1) Abridged problem statement (concise)

There are \(N\) married couples. A magician randomly matches each of the \(N\) men to a distinct woman (all \(N!\) perfect matchings equally likely). Compute the probability that **exactly \(K\)** men are matched with their true wives.

Input: integers \(K, N\) \((1 \le N \le 100,\ 0 \le K \le N)\).  
Output: `0` if probability is zero; otherwise output an irreducible fraction `A/B`.

---

## 2) Key observations

1. **A matching is a permutation.**  
   Fix the “true” pairing as man \(i\) ↔ woman \(i\). Any guessed matching corresponds to a permutation \(\pi\) where man \(i\) gets woman \(\pi(i)\).

2. **Correct couples are fixed points.**  
   Man \(i\) is correctly matched iff \(\pi(i)=i\). So we need permutations of size \(N\) with exactly \(K\) fixed points.

3. **Count = choose fixed points × derange the rest.**  
   - Choose which \(K\) positions are fixed: \(\binom{N}{K}\).
   - Remaining \(m=N-K\) elements must have **no** fixed points: a **derangement** count \(D_m\).

   Hence number of valid permutations: \(\binom{N}{K} D_{N-K}\).

4. **Probability simplifies nicely.**
   \[
   P=\frac{\binom{N}{K} D_{N-K}}{N!}
   =\frac{D_{N-K}}{K!(N-K)!}
   \]
   So we only need derangements and factorials up to 100 (big integers required).

5. **Derangements recurrence (fast, exact):**
   - \(D_0=1\)
   - \(D_1=0\)
   - \(D_m=(m-1)(D_{m-1}+D_{m-2})\) for \(m\ge 2\)

---

## 3) Full solution approach

1. Read \(K, N\). Let \(m = N-K\).
2. Compute \(D_m\) using the recurrence above.
3. If \(D_m=0\), output `0` (this happens when \(m=1\), i.e. \(K=N-1\)).
4. Compute:
   - numerator \(= D_m\)
   - denominator \(= K! \cdot m!\)
5. Reduce the fraction by \(g=\gcd(\text{numerator},\text{denominator})\).
6. Output `numerator/g` + `/` + `denominator/g`.

Complexity: \(O(N)\) arithmetic operations; values are large, so use big integers.

---

## 4) C++ implementation (detailed comments)

> Note: Standard C++ has no built-in big integers. Below uses **Boost.Multiprecision** (`cpp_int`) which is commonly available in programming contests.

```cpp
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using boost::multiprecision::cpp_int;

/*
  Compute gcd for big integers (cpp_int) via Euclid's algorithm.
*/
static cpp_int big_gcd(cpp_int a, cpp_int b) {
    while (b != 0) {
        cpp_int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

/*
  Compute factorial(n) as a big integer.
  Here n <= 100, so this is trivial.
*/
static cpp_int factorial_big(int n) {
    cpp_int res = 1;
    for (int i = 2; i <= n; ++i) res *= i;
    return res;
}

/*
  Compute derangements D_m:
    D_0 = 1
    D_1 = 0
    D_m = (m-1) * (D_{m-1} + D_{m-2}) for m >= 2
*/
static cpp_int derangements(int m) {
    if (m == 0) return 1;
    if (m == 1) return 0;

    cpp_int D0 = 1; // D_0
    cpp_int D1 = 0; // D_1
    for (int i = 2; i <= m; ++i) {
        cpp_int Di = cpp_int(i - 1) * (D1 + D0);
        D0 = D1;
        D1 = Di;
    }
    return D1; // D_m
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int K, N;
    cin >> K >> N;

    int m = N - K;              // number of elements that must NOT be fixed points
    cpp_int num = derangements(m);

    // If there are no derangements, then probability is zero.
    if (num == 0) {
        cout << 0 << "\n";
        return 0;
    }

    // Probability = D_m / (K! * m!)
    cpp_int den = factorial_big(K) * factorial_big(m);

    // Reduce to irreducible fraction.
    cpp_int g = big_gcd(num, den);
    num /= g;
    den /= g;

    cout << num << "/" << den << "\n";
    return 0;
}
```

---

## 5) Python implementation (detailed comments)

Python has built-in big integers, so this becomes very compact and safe.

```python
from math import gcd, factorial

def derangements(m: int) -> int:
    """
    D_m = number of permutations of m elements with no fixed points.
    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  # D_m

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

    m = n - k                  # elements that must be non-fixed points
    num = derangements(m)      # D_{n-k}

    if num == 0:
        print("0")
        return

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

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

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

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

This directly implements the proven formula:
\[
P = \frac{D_{N-K}}{K!(N-K)!}
\]
and outputs it in the required format.