写的大众的欧拉降幂做法，WA on #3：https://codeforces.com/contest/906/submission/235661776，码风平易近人，求大佬看看/kel

#include <bits/stdc++.h>
#define ALL(v) begin(v), end(v)
using i64 = int64_t;
using std::cin;
using std::cout;
using std::make_pair;
constexpr int N = 1e5 + 5;

int n, P, q, m;
std::array<int, N> a, phi;

auto getphi(int x) {
   auto ret{x}, xx{x};
   for (auto i = 2; (i64)i * i <= x; ++i) {
      if (xx == 1) break;
      if (xx % i) continue;
      ret = (i64)ret * (i - 1) / i;
      while (!(xx % i)) xx /= i;
   }
   if(xx > 1) ret = (i64) ret * (xx - 1) / xx;
   return ret;
}

auto qpow(int a, int b, int P) {
   auto lans{1}, la{a}, ans{1}, flag{0};
   for (; b; a = (i64)a * a % P, b >>= 1) {
      if (b & 1) {
         ans = (i64)ans * a % P;
         if (lans > ans) flag = 1;
         lans = ans;
      }
      if (la > a) flag = 1;
      la = a;
   }
   return make_pair(ans, flag);
}

auto f(int l, int r, int P, int dep) {
   auto x{make_pair(0, 0)};
   if (P == 1) return make_pair(0, 1);
   else if (a[l] == 1) return make_pair(1, 0);
   else if (l == r) {
      if (a[l] >= P) return make_pair(a[l] % P, 1);
      else return make_pair(a[l], 0);
   }
   auto y{f(l + 1, r, phi[dep], dep + 1)};
   if (y.second) y.first += phi[dep];
   return qpow(a[l], y.first, P);
}

auto main() -> int {
   std::ios::sync_with_stdio(false);
   cin.tie(nullptr), cout.tie(nullptr);

   cin >> n >> P;
   //return 0;
   for (auto x = getphi(P); x > 1; x = getphi(x)) phi[++m] = x;
   phi[++m] = 1;
   for (auto i = 1; i <= n; ++i) cin >> a[i];
   cin >> q;
   while (q--) {
      auto l{0}, r{0}; cin >> l >> r;
      cout << f(l, r, P, 1).first << "\n";
   }
   return 0;
}