我们很容易发现 $a_p$ 可以表示为 $a_1^x\times a_2\times y$ . 所以现在只需要考虑 $x, y$ 分别是什么 .

根据

$$x_1 = 1, y_1 = 0 \\ x_2 = 0, y_2 = 1 \\ \forall i\in[3, +\inf), x_i = x_{i-1}+x_{i-2}, y_i = y_{i - 1}+y_{i - 2} $$

所以 $x$ 为斐波那契数列第 $p-2$ 项， $y$ 为 $p - 1$ 。

矩阵快速幂 + 快速幂即可。

#include <cstdio>
#include <algorithm>

#define int long long

using namespace std;

const int M = 998244353;
const int P = 998244352;

struct N
{
    int cs, xs;
};

N Fibo(int n)
{
    N res, cur;
    if (n == 0)
    {
        res.cs = 0;
        res.xs = 0;
        return res;
    }
    if (n == 1)
    {
        res.cs = 1;
        res.xs = 0;
        return res;
    }
    cur = Fibo(n >> 1);
    res.cs = cur.cs * ((cur.xs << 1) % P + cur.cs) % P;
    res.xs = (cur.cs * cur.cs % P + cur.xs * cur.xs % P) % P;
    if (n & 1)
    {
        int tmp = res.cs;
        res.cs = res.xs;
        res.xs = tmp;
        (res.cs += res.xs) %= P;
    }
    return res;
} 

int n, m, k, indn, indm;

int qpow(int x, int y)
{
    if (y == 0) return 1;
    int t = qpow(x, y >> 1);
    t *= t, t %= M;
    if (y & 1) t *= x, t %= M;
    return t;
}

signed main()
{
    scanf("%lld %lld %lld", &n, &m, &k);
    indn = Fibo(k - 2).cs, indm = Fibo(k - 1).cs;
    printf("%lld\n", qpow(n, indn) * qpow(m, indm) % M);
    return 0;
}

#include <iostream>
using namespace std;
#define ll long long
ll af(int a1,int a2,ll k){
    if(k == 1) return a1;
    if(k == 2) return a2;
    return af(a1,a2,k - 1) * af(a1,a2,k - 2) % 998244352;
}
int main(){
    int a1,a2;ll k;
    cin >> a1 >> a2 >> k;
    cout << af(a1,a2,k);
    return 0;
}

这样会超时+内存超限，所以不建议递归。。。