Finding inverse

#include <bits/stdc++.h>

using namespace std;

long long gcd(long long a, long long b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

bool coprime(long long a, long long b) {
    return gcd(a, b) == 1;
}

long long eulers_totient_function(long long n) {
    long long count = 0;
    for (long long k = 1; k < n; ++k) {
        if (coprime(k, n))
            ++count;
    }
    return count;
}


long long module_exponentiation(long long a, long long b, long long MOD) {
    if (b == 0) 
        return 1%MOD;
    else if (b%2 == 0) {
        long long half = module_exponentiation(a, b / 2, MOD) % MOD;
        return (half * half) % MOD;
    }
    else {
        return (module_exponentiation(a, b - 1, MOD) % MOD * a) % MOD;
    }
}

long long modular_inverse(long long a, long long MOD) {
    if (!coprime(a, MOD))
        return -1;
    long long phiMOD = eulers_totient_function(MOD);
    long long inverse = module_exponentiation(a, phiMOD - 1, MOD);
    return inverse;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    long long a, MOD;
    cin >> a >> MOD;

    cout << modular_inverse(a, MOD) << "\n";
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: TIME LIMIT EXCEEDED

Test 13

Verdict: TIME LIMIT EXCEEDED

Test 14

Verdict: ACCEPTED