I have found these articles, where it's already described:

https://mirror.codeforces.com/blog/entry/72527

https://mirror.codeforces.com/blog/entry/46620

They are both very good, but I want to write a more concise blog about the modular inverse specifically, as it is needed in many problems that don't even belong to number theory.

The Problem

There are two integer numbers A and B. Suppose you know that A is divisible by B. But they are very big, so you only know their remainders modulo some prime number M: A % M and B % M. You want to know the remainder of their quotient – (A / B) % M. But (A % M) may be not divisible by (B % M). What to do?

Such question is very common in combinatorical problems, for example when counting binomial coefficients, where you need to divide n! by k! and (n - k)!.

The solution

The short answer is you need to calculate B to the power of M - 2 modulo M (using binary exponentiation). The resulting number is called the modular inverse of B. Now you can multiply A by it to effectively divide it by B.

Note: this only works if B % M is not 0 and M is prime.

The implementation

#include <bits/stdc++.h>

using namespace std;

const int mod = 998244353;

int bin_exp(int a, int b) {
    if (b == 0) {
        return 1;
    }
    if (b % 2) {
        return bin_exp(a, b - 1) * 1LL * a % mod;
    }
    int res = bin_exp(a, b / 2);
    return res * 1LL * res % mod;
}

int inv(int a) {
    return bin_exp(a, mod - 2);
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int a, b;
    cin >> a >> b;
    cout << a * 1LL * inv(b) % mod << '\n';
}

#include <bits/stdc++.h>

using namespace std;

#define int int64_t

const int mod = 998244353;

int bin_exp(int a, int b) {
    if (b == 0) {
        return 1;
    }
    if (b % 2) {
        return bin_exp(a, b - 1) * a % mod;
    }
    int res = bin_exp(a, b / 2);
    return res * res % mod;
}

int inv(int a) {
    return bin_exp(a, mod - 2);
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int a, b;
    cin >> a >> b;
    cout << a * inv(b) % mod << '\n';
}

The Proof

This is a well-known formula that relies on Fermat's little theorem and the fact that every non-zero element of the ring of remainders modulo prime number has exactly one multiplicative inverse. If you want to know more, you can read the aforementioned articles.