What is the fastest known time complexity for computing central trinomial coefficients?

Let $C_n=1,1,3,7,19,51,…$ (OEIS A002426) denote the coefficient of $x^n$ in $(x^2+x+1)^n$ starting at $n=0$.

It can be shown that, if $n$ is prime, then $C_n=1 pmod n$, because by the binomial theorem

$$(x + y)^n=sum_{k=0}^{n} binom{n}{k}y^kx^{n-k}=x^n+y^npmod n$$ so that

$$(x^2+x+1)^n = x^2+x+1pmod n$$

follows.

The computational complexity problem I am aiming on solving is, given a large integer $n$ (say, about RSA size), I would like to verify that the congruence

$C_n=1pmod n$

in polynomial time analogous to how $x^n=x pmod n$ can be computed using binary exponentiation.

Thanks for help.