首先可以发现 $\gcd(a^n-1,a^m-1)=\gcd(a^n-1,a^m-a^{m-n}+a^{m-n}-1)=\gcd(a^n-1,a^{m-n}-1)$，也就是可以在指数上辗转相除，所以 $\gcd(a^n-1,a^m-1)=a^{\gcd(n,m)}-1$。

继续求 $\gcd(F_n,F_m)$。首先显然 $\gcd(F_n,F_{n+1})=\gcd(F_n,F_{n-1})=1$，结合 $F_{n+m}=F_nF_{m+1}+F_{n-1}F_m$，于是有 $$ \begin{aligned} \gcd(F_n,F_m)&=\gcd(F_n,F_{m-n}F_{n+1}+F_{m-n-1}F_n)\\ &=\gcd(F_n,F_{m-n}F_{n+1})\\ &=\gcd(F_n,F_{m-n}) \end{aligned} $$ 所以同样有 $\gcd(F_n,F_m)=F_{\gcd(n,m)}$。

设 $\gcd(x,y)=g$，我们分别计算 $\frac{a^{F_x}-1}{a^{F_g}-1}$ 和 $\frac{a^{F_y}-1}{a^{F_g}-1}$ 并相乘。

把 $m$ 分解质因数，对每个 $p^e$ 分别求解，最后用中国剩余定理合并。

现在要计算的是 $\frac{a^{F_{kn}}-1}{a^{F_{n}}-1}\bmod p^e$，我们先分别算出分子和分母。这里因为指数非常大，要用到欧拉定理，对 $\varphi(p^e)=(p-1)p^{e-1}$ 取模（当然，因为 $a$ 和 $p^e$ 不一定互素，不能让大的指数取模后变得太小）。

如果分母不是 $p^e$ 的倍数，那么设分母中的 $p$ 的个数为 $k$，我们重新计算分子分母 $\bmod p^{e+k}$ 的值，然后直接同时除掉 $p^k$，这样分母就和 $p$ 互素了，直接求逆元即可。

如果分母是 $p^e$ 的倍数，即 $a^n\equiv 1\pmod {p^e}$，我们注意到 $\frac{a^{kn-1}}{a^n-1}=1+a^n+a^{2n}+\cdots+a^{(k-1)n}\equiv k\pmod {p^e}$，所以我们只需要计算 $\frac{F_{kn}}{F_n}$。

注意到 $F_0,F_n,F_{2n},\ldots$ 仍然是二阶线性递推，这是因为设 $\phi$ 和 $\psi$ 分别是 $x^2-x-1=0$ 的两根，则 $F_0,F_n,F_{2n},\ldots$ 的递推式的两个根就是 $\phi^n$ 和 $\psi^n$，利用韦达定理可以直接算出递推式的系数（关于 $n$ 是一个类斐波那契数列），然后递推即可。

时间复杂度主要来源于质因数分解，后面部分的时间复杂度大约是 $O(\log ^2m)$。