概要
解法
$p$ を素数とし，$\bmod p$ での合同式（$\mathbb{F}_p$ での等式）を単に等号で書きます．
Fibonacci 数列の周期
以下 $p=998244353$ とします．Fibonacci 数列 $\{F_n\}$ を初期値 $F_0=0,F_1=1$ と漸化式 $F_n=F_{n-1}+F_{n-2}$ によって定めます．
$F$ は周期 $2p+2$ を持ちます．つまり $L=2p+2$ とすると任意の $i$ に対して $F_{L+i}= F_i$ が成り立ちます．
一般により強く，素数 $p$ に対して Fibonacci 数列の周期のひとつを与えることができますが，後述します．$p=998244353$ の場合に周期を求めるだけであれば，$F_n=0,F_{n+1}=1$ となる $n$ を愚直なループで見つければよいです．
本問題の数列の周期
数列 $\{p_n\},\{q_n\}$ を $p_0=1,q_0=0,p_1=0,q_1=1,p_{n}=p_{n-1}+p_{n-2},q_{n}=q_{n-1}+q_{n-2}$ により定めます．このとき次が成り立ちます：
$a_0=X,a_1=Y,a_{n}=a_{n-1}+a_{n-2}$ で定まる $\{a_n\}$ について $a_n=p_nX+q_nY$．
証明は数学的帰納法で容易です．また定義を先に与えましたが，結論が成り立つような $p,q$ を定めようとするとこの定義に至ることは容易だと思います．
$p,q$ は Fibonacci 数列のシフトなので，これらも周期 $2p+2$ を持ちます．したがって本問の数列 $\{a_n\}$ も周期 $2p+2$ を持ちます．
本問の解法
$L=2p+2$ とします．周期性を使うと，次の問題を高々 $2$ 回解けばよいことが分かります．
- $X,Y,N$ が与えられる．ただし $N\leq L$ である．$a_0=X,a_1=Y,a_n=a_{n-1}+a_{n-2}$ で定まる数列 $a$ について，$\prod_{0\leq i<N}a_i$ を求めよ．
適当なバケットサイズ $B$ をとり上で登場した数列 $p_n,q_n$ を $B$ 項程度前計算しておきます．すると，$a_i,a_{i+1}$ から $a_{i+B},a_{i+1+B}$ を計算することが $O(1)$ 時間でできるようになります．添字が $[kB, kB+B)$ の部分をまとめて扱うことを考えると，次のような計算が $N/B$ 回程度できればよいことになります：
- $X,Y$ が与えられるので，$a_0=X,a_1=Y,a_n=a_{n-1}+a_{n-2}$ で定まる数列 $a$ について，$\prod_{0\leq i<B}a_i$ を求めよ．
総積を求める項数が定数になりました．$a_i=p_iX+q_iY$ であることを思い出せば，求めるべきは
$\prod_{0\leq i<B}(p_iX+q_iY)=X^B\prod_{0\leq i<B}(p_i+q_it)$ （ただし $t=Y/X$）
となります（$X=0$ のときは $a_0=0$ なので積は $0$ です）．
よって $F(t) = \prod_{0\leq i<B}(p_i+q_it)$ に対して多点評価を行えばこれらの計算ができます．
$B=\sqrt{p}$ ととった場合計算量は，計算量 $O(\sqrt{p}\log^2p)$ となっていると思います．
参考：Fibonacci 数列の周期
前提
$p=2,5$ のときは例外処理になります．以下 $p$ を $2,5$ ではない素数とします．次を示します．
- $p\equiv 1,4\pmod{5}$ のとき，Fibonacci 数列は $p-1$ を周期に持つ．
- $p\equiv 2,3\pmod{5}$ のとき，Fibonacci 数列は $2p+2$ を周期に持つ．
主張は「周期 xxx を持つ」であって「最小周期が xxx である」ではないことに注意してください．
また，平方剰余の性質として知られている次を仮定します：
- $p\equiv 1,4\pmod{5}$ のとき，$5$ は $p$ を法として平方剰余である．したがって $5=t^2$ を満たす $t$ が存在する．$5^{(p-1)/2}\equiv 1\pmod{p}$ が成り立つ．
- $p\equiv 2,3\pmod{5}$ のとき，$5$ は $p$ を法として平方非剰余である．したがって $5=t^2$ を満たす $t$ は存在しない．$5^{(p-1)/2}\equiv -1\pmod{p}$ が成り立つ．
$a^{(p-1)/2} \bmod p$ と 平方剰余の関係は Euler 規準として知られており，原始根の存在を認めるとすぐに分かります．平方非剰余の判定はやや非自明です．詳しく知りたい場合は「平方剰余の相互法則」という検索ワードで調べてみてください．
$p\equiv 1,4\pmod{5}$ の場合
整数 $t$ を $t^2\equiv 5\pmod{p}$ が成り立つようにとります（上に述べたように存在する）．
このとき，$a=\frac{1+t}{2},b=\frac{1-t}{2}$ とすると $a\neq b$ かつ $F_n=\frac{a^n-b^n}{a-b}$ となることが分かります．よって $F_n$ が周期 $p-1$ を持つことを示すには $a^n,b^n$ が周期 $p-1$ を持つことを示せばよく，これは Fermat の小定理として知られている通りです．
$p\equiv 2,3\pmod{5}$ の場合
不定元 $t$ をとり，$A=\mathbb{F_p}[t]/(t^2-5)$ とします．別の言い方をすれば，
$A=\{a+bt\mid 0\leq a,b\leq p-1\}$ に，多項式の積と $t^2=5$ が成り立つように演算を入れることを考えます．
するとやはり，$a=\frac{1+t}{2}$, $b=\frac{1-t}{2}$ に対して $t F_n = a^n-b^n$ が成り立つことが帰納的に証明できます．$t$ が可逆元であることも証明できるので，$F_n$ が周期 $2p+2$ を持つことを示すには $a^n,b^n$ が周期 $2p+2$ を持つことを示せばよいです．
$\bmod p$ で考えているときに二項定理から $(x+y)^p=x^p+y^p$ などが成り立つことを踏まえると，
$$a^p=\frac{1^p+t^p}{2^p}=\frac{1+5^{(p-1)/2}t}{2}=\frac{1-t}{2}=b$$
となるので $a^{p+1}=ab=-1$．よって $a^{2p+2}=1$ が成り立ちます．同様に $b^{2p+2}=1$ も成り立ちます．
参考
有限体の Galois 理論など知識があるとより簡潔に考察できると思います．目標は $x^2-x-1=0$ の $2$ 解 $a,b$ について $a^{2p+2}=1$ を示すことです．
$\mathbb{F}_p$ で $x^2-x-1=0$ の解が存在しないとき，この方程式の解をその $2$ 次拡大 $\mathbb{F}_q=\mathbb{F}_{p^2}$ にとることができます．
$p$ 乗写像 $\mathbb{F}_q\longrightarrow \mathbb{F}_q$ は非自明な $\mathbb{F}_p$ 同型です．$2$ 次拡大におけるそのような写像は唯一で，これは $a,b$ を入れ替えます．よって $a^p=b, a^{p+1}=ab=-1, a^{2p+2}=1$ が成り立ちます．
