Problem 812

Dynamical Polynomials

A dynamical polynomial is a monic polynomial $f (x)$ with integer coefficients such that $f (x)$ divides $f (x^{2} - 2)$ .

For example, $f (x) = x^{2} - x - 2$ is a dynamical polynomial because $f (x^{2} - 2) = x^{4} - 5 x^{2} + 4 = (x^{2} + x - 2) f (x)$ .

Let $S (n)$ be the number of dynamical polynomials of degree $n$ .

For example, $S (2) = 6$ , as there are six dynamical polynomials of degree 2:
$x^{2} - 4 x + 4 x^{2} - x - 2 x^{2} - 4 x^{2} - 1 x^{2} + x - 1 x^{2} + 2 x + 1$
Also, $S (5) = 58$ and $S (20) = 122087$ .

Find $S (10 000)$ . Give your answer modulo $998244353$ .

动态多项式

若首一整系数多项式 $f (x)$ 整除 $f (x^{2} - 2)$ ，则称之为动态多项式。

例如， $f (x) = x^{2} - x - 2$ 是动态多项式，因为 $f (x^{2} - 2) = x^{4} - 5 x^{2} + 4 = (x^{2} + x - 2) f (x)$ 。

记 $S (n)$ 为最高次数为 $n$ 的动态多项式的数目。

例如， $S (2) = 6$ ，因为共有六个最高次数为 $2$ 的动态多项式：
$x^{2} - 4 x + 4 x^{2} - x - 2 x^{2} - 4 x^{2} - 1 x^{2} + x - 1 x^{2} + 2 x + 1$
已知 $S (5) = 58$ ， $S (20) = 122087$ 。

求 $S (10 000)$ ，并将你的答案对 $998244353$ 取余。