#include <bits/stdc++.h>

using namespace std;

int exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

// 快速幂 (a^k)%p
int qmi(int a, int k, int p) {
    int res = 1;
    while (k) {
        if (k & 1) res = res * a % p;
        k >>= 1;
        a = a * a % p;
    }
    return res;
}
// https://blog.csdn.net/weixin_42759798/article/details/99451434

// 逆元（费马小定理法）
// https://blog.csdn.net/qq_45863710/article/details/107424938

// https://blog.csdn.net/f1932460873/article/details/81193462
int main() {
    // 1、扩展欧几里得求逆元
    //  5*7 mod 3 的逆元

    //
    int x, y;
    exgcd(5 * 7, 3, x, y);

    cout << (x + 3) % 3 << endl;

    // 2、费马小定理求逆元使用场景
    cout << qmi(5 * 7, 3 - 1, 3) << endl;
    return 0;
}