　解説中の合同式は全て $p$ を法として考える. 

----
**補題1.**　問題文の一つ目の条件は,  $1$ 以上 $p-1$ 以下の整数 $y$ が存在して $y + y^{-1} \equiv c$ を満たすことと同値である. \
**証明.**　後者は $y^2 - cy + 1 \equiv 0$ となる整数 $y$ の存在と同値. この両辺を $4$ 倍して平方完成すればよい.　(証明終) 

----
　$y + y^{-1} \equiv c$ が成り立つとき, 数列 $F_0, F_1, \ldots$ を
$$F_0 = 0, \quad F_1 = 1, \quad F_{k+2} = F_{k+1} +F_k  \quad (k = 0, 1, \ldots)$$
で定めると, $a_k \equiv y^{F_k} + y^{- F_k}$ であることが帰納的に分かる. $F_{18} = 2584$ より, $a_{18} \equiv y^{2584} + y^{-2584}$ である. したがって, 補題1より求める値は $y^{2584} + y^{-2584}$ を $p$ で割った余りの種類数と一致する. \
　ここで, 法 $p$ における原始根の一つを $g$ とおくと, $\gcd(p-1, 2584) = 136$ より, 
$$1^{2584},\quad 2^{2584},\quad \ldots, \quad (p-1)^{2584}$$
を $p$ で割った余りは全て $g^{136 i} \pmod{p}~(0 \leq i \leq 2^{20} \times 7 - 1)$ の形で表されることに注意する.

----
**補題2.**　相異なる $1$ 以上 $p-1$ 以下の整数 $a$, $b$ が $a + a^{-1} \equiv b + b^{-1}$ を満たすとき, $a \equiv b^{-1}$ である. \
**証明.**　両辺を $a$ 倍して変形すると, 以下を得る. $a \neq b$ より, $a \equiv b^{-1}$ である.　(証明終) 
$$(a - b)(a - b^{-1}) \equiv 0$$

----
　補題2より, 求める値は $g^{136 i} \pmod{p}$ に対し, $p$ を法とした逆元になる数同士をペアにしたときのペアの個数と一致する. $i=0, 2^{19} \times 7$ のとき (すなわち $g^{136 i} \equiv  \pm 1$ のとき) に限り自分自身とペアを組むから, 答えは 
$$(2^{20} \times 7 - 2)\/2 + 2 = 2^{19} \times 7 +1 = \textbf{3670017}.$$
公式解説
https://onlinemathcontest.com/contests/omc106/editorial/2987
　素数 $p$ を $p = 998244353 (= 2^{23} \times 7 \times 17 + 1) $ で定めます．$0$ 以上 $p-1$ 以下の整数 $n$ のうち，以下の条件を満たす整数 $c$ が存在するものの個数を求めてください．
- $c^2 - 4 \equiv x^2 \pmod{p}$ となる整数 $x$ が存在する．
- 整数列 $a_0, a_1, \ldots$ を以下で定めると， $a_{18} \equiv n \pmod{p}$ が成立する．
$$a_0 = 2, \quad a_1 = a_2 =c, \quad a_{k+3} = a_{k+2} a_{k+1} - a_k  \quad (k = 0, 1, \ldots)$$