Остаток числа в степени по модулю

Такая проблема: код работает некорректно. Неправильный остаток. Когда второй раз возводим число N в степень (28 или 29 строка) и если оно больше чем int, то вместо возведения в степень число приравнивается к int min или int max, не смотря на то, что используется long. Или, другими словами, для всех очень больших с плюсом или минусом чисел остаток будет вычисляться не для них, а для int min и int max. Надеюсь, понятно. Подскажите, пожалуйста, как исправить?

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<locale.h>
void ConvertionNumber(long *, long);
void SelectMinus(long *, long, long *);
void ConvertionPower(long *, long *);
long CheckSimpleNumber(long);
int main()
{
  setlocale(LC_ALL, "Rus");
  long N, P, M;
    printf("Введите число:\n"); // ввод данных
  scanf_s("%ld", &N);
  printf("Введите степень:\n");
  scanf_s("%ld", &P);
  printf("Введите модуль:\n");
  scanf_s("%ld", &M);
  long Z = 1;
  SelectMinus(&N, P, &Z); // положительное число или отрицательное, если отрицательное и степень 
нечетная   
  выделяем "-1" и работаем с модулем числа 
  ConvertionNumber(&N, M); // уменьшаем число
  SelectMinus(&N, P, &Z); // положительное число или отрицательное, если отрицательное и степень 
нечетная 
  выделяем "-1", преобразовуем знак и работаем с модулем числа
  long p = 1;
  ConvertionPower(&P, &p); // преобразованиe степени до простой
  if (P < p) N = pow(N, P); // возводим число в наименьшую степень
  else N = pow(N, p);
  ConvertionNumber(&N, M); // уменьшаем число
  if (P > p) N = pow(N, P); // возводим число в большую степень
  else N = pow(N, p);
  long Ost=(Z * N)%M;
  if (Ost < 0) Ost += M;
  printf("Остаток равен %ld\n", Ost);
  system("pause");
  return 0;
}
void ConvertionNumber(long *n, long m)
{
  if (fabs(*n) >= m)
  {
    long N1 = *n % m;
    long N2 = (*n % m) - m;
    if (fabs(N1) < fabs(N2)) *n = N1;
    else *n = N2;
  } 
}
void SelectMinus(long *n, long p, long *z)
{
  if ((*n < 0) && (p % 2 == 1))  *z = *z*(-1);
  *n = fabs(*n);
}
void ConvertionPower(long *P, long *p)
{
  long i = 2;
  while (CheckSimpleNumber(*P) == 0)
  {
    if (*P % i == 0)
    {
      *P = *P / i;
      *p = *p * i;
    }
    i++;
  }
}
long CheckSimpleNumber(long n)
{
  long i = 2, c = 1;
  while (i <= sqrt(n))
  {
    if (n%i == 0) c = 0;
    i++;
  }
  return c;
}