OMC106(E)

点数: 700

Writer: sqrt_3

　素数 $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)$$