Modular multiplicative inverse

Question

I calculating ((A^B)/C)%M, but my code is not working when A,B,C,M are large in numbers. This code is giving right answer when A,B,C,D is small int.

What is wrong here?

Here C and M is co-prime

Sample input 2 3 4 5 Sample output 2

Code fails for these input 969109092 60139073 122541116 75884463

C program

#include <stdio.h>

int d,x,y;

Modular exponential (A^B)%M

int power(int A, int B, int M)
{
    long long int result=1;
    while(B>0)
    {
        if(B % 2 ==1)
        {
            result=(result * A)%M;
        }
        A=(A*A)%M;
        B=B/2;
    }
    return result;
}

Modular multiplicative inverse

void extendedEuclid(int A, int B)
{
    if(B == 0)
    {
        d = A;
        x = 1;
        y = 0;
    }
    else
    {
        extendedEuclid(B,A%B);
        int temp = x;
        x = y;
        y = temp - (A/B)*y;
    }
}

int modInv(int A, int M)
{
    extendedEuclid(A,M);
    return (x%M+M)%M;
}

main()

int main()
{
    int A,B,C,M;
    scanf("%d %d %d %d",&A,&B,&C,&M);
    int inv = modInv(C,M)%M;
    printf("%d\n",inv);
    long long int p = (power(A,B,M))%M;
    printf("%d\n",p);
    long long int ans = (p * inv)%M;
    //printf("%d",((modInv(C,M)*(power(A,B,M))))%M);
    printf("%lld",ans);
    return 0;
}

Answer 1

Test version with fixes noted in comments:

#include <stdio.h>

int d,x,y;

int power(int A, int B, int M)
{
    long long int result=1;
    long long int S = A;            /* fix */
    while(B>0)
    {
        if(B % 2 ==1)
        {
            result=(result * S)%M;  /* fix */
        }
        S=(S*S)%M;                  /* fix */
        B=B/2;
    }
    return (int)result;
}

void extendedEuclid(int A, int B)
{
int temp;                           /* C */
    if(B == 0)
    {
        d = A;
        x = 1;
        y = 0;
    }
    else
    {
        extendedEuclid(B,A%B);
        temp = x;
        x = y;
        y = temp - (A/B)*y;
    }
}

int modInv(int A, int M)
{
    extendedEuclid(A,M);
/*  x = x%M;                        ** not needed */
    if (x < 0)                      /* fix */
        x += M;                     /* fix */
    return (x);                     /* fix */
}

int main()
{
    int A,B,C,M;                    /* C */
    int inv, p, ans;                /* C */
    A = 969109092;                  /* 2^2 × 3^2 ×7 × 1249 × 3079 */
    B =  60139073;                  /* 60139073 */
    C = 122541116;                  /* 2^2 × 1621 × 18899 */
    M =  75884463;                  /* 3^2 × 8431607 */

    inv = modInv(C,M)%M;            /* 15543920 */
    printf("%d\n",inv);
    p = power(A,B,M)%M;             /*  6704397 */
    printf("%d\n",p);
    ans = (unsigned)(((unsigned long long)p * inv)%M);  /* fix 22271562 */
    printf("%d\n",ans);
    return 0;
}